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

非递归版本

中序顺序是左-根-右
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
        

###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