1. 树的遍历

前序遍历

前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树。

image.png

中序遍历

中序遍历是先遍历左子树，然后访问根节点，然后遍历右子树。

image.png

通常来说，对于二叉搜索树，我们可以通过中序遍历得到一个递增的有序序列

后序遍历

后序遍历是先遍历左子树，然后遍历右子树，最后访问树的根节点。

image.png

2. 递归

使用递归方法时，只需更改获取root.val的位置。

前序遍历

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        self.res = []
        return self.preorder(root)
        
    def preorder(self, root):
        if not root: return []
        # 前序：root -> left -> right
        self.res.append(root.val) 
        self.preorder(root.left)
        self.preorder(root.right)
        return self.res

中序遍历

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        self.res  = []
        return self.inorder(root)
    
    def inorder(self, root):
        if not root: return []
        # 中序： left -> root -> right
        self.inorder(root.left)
        self.res.append(root.val)
        self.inorder(root.right)
        return self.res 

后序遍历

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        self.res  = []
        return self.postorder(root)
    
    def postorder(self, root):
        if not root: return []
        # 后序： left -> right -> root 
        self.postorder(root.left)
        self.postorder(root.right)
        self.res.append(root.val)
        return self.res

3. 迭代

第一种模板

前序遍历

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root: return []
        stack = [root]
        res = []
        while stack:
            node = stack.pop()
            res.append(node.val)
            if node.right:
                stack.append(node.right)            
            if node.left:
                stack.append(node.left)    
        return res

后序遍历

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if not root: return []
        stack = [root]
        res = []
        while stack:
            node = stack.pop()
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
            res.append(node.val)
        return res[::-1]  # 逆序输出

中序遍历

中序遍历最常用模板

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root: return []
        res = []
        stack = []
        node = root
        while node or stack:
            while node:
                stack.append(node)
                node = node.left
            node = stack.pop()
            res.append(node.val)
            node = node.right
        return res

第二种模板

class Solution:
    # 前序遍历
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root: return []
        node = root 
        stack = []
        res = []
        while node or stack:
            while node:
                res.append(node.val)
                stack.append(node)
                node = node.left # <- left
            node = stack.pop()
            node = node.right # <- right
        return res 

    # 后序遍历
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if not root: return []
        node = root
        stack = []
        res = []
        while node or stack:
            while node:
                res.append(node.val)
                stack.append(node)
                node = node.right # <- right
            node = stack.pop()
            node = node.left # <- left
        return res[::-1] # 同样需要逆序输出

    # 中序遍历
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root: return []
        node = root
        stack = []
        res = []
        while node or stack:
            while node:
                stack.append(node)
                node = node.left
            node = stack.pop()
            res.append(node.val)
            node = node.right
        return res