二叉树的前中后三种遍历(递归、非递归和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 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.
# 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
        

非递归版本

# 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
        

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