二叉树的前中后三种遍历(递归、非递归和Morris)

· 约 5 分钟阅读 · – 次阅读 leetcode
#binary-tree

前序遍历

递归版本

递归的一个思想就是：假设子问题已经解决。 对于遍历来说，就是左子树的结果已经知道了，右子树的结果也已经知道了

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        if not root:
            return result
        result.append(root.val)
        result += self.preorderTraversal(root.left)
        result += self.preorderTraversal(root.right)
        return result

非递归版本

根-左-右，使用栈的思路。 核心要点，访问完根节点后，考虑栈先进后出的特点，需要先将右子树压栈，再将左子树压栈。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        if not root:
            return result
        stack = [root]
        while stack:
            cur = stack.pop()
            result.append(cur.val)
            if cur.right:
                stack.append(cur.right)
            if cur.left:
                stack.append(cur.left)
        return result


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        if (root == nullptr) return ans;
        TreeNode* p = nullptr;
        stack<TreeNode*> sk;
        sk.emplace(root);
        while(!sk.empty()) {
            p = sk.top();
            sk.pop();
            ans.emplace_back(p->val);
            if(p->right) {
                sk.emplace(p->right);
            }
            if(p->left) {
                sk.emplace(p->left);
            }
        }
        return ans;
    }
};

94. 二叉树的中序遍历

递归版本

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        if not root:
            return result
        result += self.inorderTraversal(root.left)
        result.append(root.val)
        result += self.inorderTraversal(root.right)
        return result

非递归版本

中序顺序是左-根-右 1.先将根节点入栈，然后将左节点持续入栈，直至叶子节点。 2.出栈访问，然后同样的方式该节点的右节点

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        if not root:
            return result
        stack = []
        p = root
        while stack or p:
            # 将先根入栈，然后左节点入栈
            while p:
                stack.append(p)
                p = p.left
            # 左节点为空，根节点此时可以出栈，然后再看该节点的右节点
            p = stack.pop()
            result.append(p.val)
            p = p.right
        return result

上次是2022-04-10，时隔7个月的2022-12-20，能用21分钟写出C++版本的非递归中序，还是挺欣慰的

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        if (root == nullptr) return ans;
        stack<TreeNode*> sk;
        TreeNode *p = root;
        // 栈不空或者p不空
        while (!sk.empty() || p) {
            // 将p的左子节点全部压栈，直到遇到叶子结点
            while (p) {
                sk.emplace(p);
                p = p->left;
            }
            // 此时p为空，需要弹出栈顶元素访问，然后访问柚子树
            if (!p && !sk.empty()) {
                p = sk.top();
                sk.pop();
            }
            ans.emplace_back(p->val);
            p = p->right;
        }
        return ans;

    }
};

###Morris 遍历待补充

后序遍历

递归版本

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        if not root:
            return result
        result += self.postorderTraversal(root.left)
        result += self.postorderTraversal(root.right)
        result.append(root.val)
        return result

非递归版本

搞懂了以后也比较简单，和中序遍历比较类似， 不同的是后序遍历在右子树存在时需要先临时将根入栈，待右子树都处理完以后才能将根节点入栈。

这里面有个冲突就是：当判断某个根节点是否该被访问还是先将右子树进行访问的时候无法区分右子树是否已被访问过，所以需要一个prev标记一下。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        if not root:
            return result
        stack = []
        p = root
        prev = None
        while stack or p:
            while p:
                stack.append(p)
                p = p.left
            p = stack.pop()
            # 如果上一次访问过p的右子树或者右子树不存在
            if prev == p.right or not p.right:
                result.append(p.val)
                prev = p
                p = None
            else:
                stack.append(p)
                p = p.right
        return result

        return result
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;
        if (root == nullptr) return ans;
        stack<TreeNode*> sk;
        TreeNode *p = root, *prev = nullptr;
        while (!sk.empty() || p) {
            while(p){
                sk.emplace(p);
                p = p->left;
            }
            if (!p && !sk.empty()) {
                p = sk.top();
                // 需要看一眼栈顶元素，若其右子树为空，或已被访问，则此时才能访问跟节点，否则需要先处理右子树
                if (!p->right || prev == p->right){
                    ans.emplace_back(p->val);
                    sk.pop();
                    prev = p;
                    p = nullptr;  // 此时需要将p设置为空，否则会持续访问p
                }else{
                    p = p->right;
                }
            }
        }
        return ans;

    }
};