LeetCode——二叉树的前中后序遍历

二叉树主要有两种遍历方式：

• 深度优先遍历：先往深走，遇到叶子节点再往回走。
• 广度优先遍历：一层一层的去遍历，也就是常说的层遍历。

在深度优先遍历中：有三个顺序，前中后序遍历，这中间的”前中后”指的是遍历父节点的先后顺序，且左节点永远在右节点前面遍历。

• 前序遍历(父左右)：F、B、A、D、C、E、G、I、H。

• 中序遍历(左父右)：A、B、C、D、E、F、G、H、I。

• 后序遍历(左右父)：A、C、E、D、B、H、I、G、F。

图片来源：https://zh.m.wikipedia.org/wiki/%E6%A0%91%E7%9A%84%E9%81%8D%E5%8E%86
在树的遍实现方法中，有两种比较主流：迭代和递归。下面以力扣的三道题目作为例子：

• 144.二叉树的前序遍历
• 94.二叉树的中序遍历
• 145.二叉树的后序遍历

递归：

# 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]:
        answer = []
        def dfs(node) :
            if node is None :
                return 
            
            answer.append(node.val)
            dfs(node.left)
            dfs(node.right)

        dfs(root)
        return answer
 
 #中序
 class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        answer = []
        def dfs(node) :
            if node is None :
                return 

            dfs(node.left)
            answer.append(node.val)
            dfs(node.right)

        dfs(root)
        return answer

#后序
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def dfs(node) :
            if node is None :
                return 
            
            dfs(node.left)
            dfs(node.right)
            answer.append(node.val)

        answer = []
        dfs(root)
        return answer

迭代：

# 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]:
        if root is None :
            return []
        
        stack = []
        result = []

        stack.append(root)
        while stack :
            node = stack.pop()
            result.append(node.val)

            if node.right :
                stack.append(node.right)
            
            if node.left :
                stack.append(node.left)

        return result

#中序
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root is None :
            return []

        result = []
        stack = []
        curr = root 

        while curr or stack :
            #访问最左边节点
            if curr :
                stack.append(curr)
                curr = curr.left
            
            else :
                node = stack.pop()
                result.append(node.val)
                #访问栈顶元素的右边节点
                curr = node.right
        
        return result

#后序
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root is None :
            return []

        result = []
        stack = []
        stack.append(root)

        while stack :
            node = stack.pop()
            result.append(node.val)

            if node.left :
                stack.append(node.left)
            
            if node.right :
                stack.append(node.right)

        return result[ : : -1]