1. 樹的遍歷

前序遍歷

前序遍歷首先訪問根節(jié)點铜犬，然后遍歷左子樹，最后遍歷右子樹霞揉。

image.png

中序遍歷

中序遍歷是先遍歷左子樹旬薯，然后訪問根節(jié)點，然后遍歷右子樹适秩。

image.png

通常來說绊序，對于二叉搜索樹，我們可以通過中序遍歷得到一個遞增的有序序列

后序遍歷

后序遍歷是先遍歷左子樹秽荞，然后遍歷右子樹骤公，最后訪問樹的根節(jié)點。

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