二叉树的遍历

掌握两种方法进行二叉树的遍历，这里重点看迭代法是怎么写，迭代法使用栈来模拟递归中的栈，也可以使用一种通用方式进行前、中、后序遍历。

递归法

def dfs(root) {
    // 前序遍历
    dfs(root.left)
    // 中序遍历
    dfs(root.right)
    // 后序遍历
}

迭代法：迭代法是用 stack 栈来模拟递归栈

下面这种写法可以统一前序、中序、后序遍历方式的写法，只需要改变入栈顺序

前序遍历：中，左，右
中序遍历：左，中，右
后序遍历：左，右，中

中序遍历：
栈是一种 先进后出的结构，出栈顺序为左，中，右
那么入栈顺序必须调整为倒序，也就是右，中，左

同理，如果是前序遍历，入栈顺序为 右，左，中；后序遍历，入栈顺序 中，右，左

有没有发现？迭代法入栈顺序与递归法的递归顺序正好相反！

while stack:
    node = stack.pop()
    if node == None:
        continue
    if isinstance(node, int):
        ans.append(node)
    else:
        # 中序遍历
        stack.extend([node.right, node.val, node.left])
        # 前序遍历
        # stack.extend([node.right, node.left, node.val])
        # 后序遍历
        # stack.extend([node.val, node.right, node.left])

• 每个节点都只入栈一次，出栈一次

中序遍历

94. 二叉树的中序遍历

递归法：

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = []

        def dfs(root):
            if root == None:
                return
            dfs(root.left)
            ans.append(root.val)
            dfs(root.right)
        dfs(root)
        return ans

迭代法：迭代法是用 stack 栈来模拟递归栈

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        stack = [root]
        while stack:
            node = stack.pop()
            if node == None:
                continue
            if isinstance(node, int):
                ans.append(node)
            else:
                stack.extend([node.right, node.val, node.left])
        return ans

前序遍历

递归

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        def dfs(root):
            if root==None:
                return
            ans.append(root.val)
            dfs(root.left)
            dfs(root.right)
        dfs(root)
        return ans

迭代

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        stack = [root]
        while stack:
            node = stack.pop()
            if node == None:
                continue
            if isinstance(node, int):
                ans.append(node)
            else:
                stack.extend([node.right, node.left, node.val])
        return ans

后序遍历

145. 二叉树的后序遍历

递归

class Solution:
    def postorderTraversal(self,root:Optional[TreeNode])->List[int]:
        ans= []
        def dfs(root):
            if root==None:
                return
            dfs(root.left)
            dfs(root.right)
            ans.append(root.val)
        dfs(root)
        return ans

迭代

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        stack = [root]
        while stack:
            node = stack.pop()
            if node == None:
                continue
            if isinstance(node, int):
                ans.append(node)
            else:
                stack.extend([node.val, node.right, node.left])
        return ans

层次遍历

层次遍历需要借助队列进行层次遍历

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root == None:
            return []
        ans = []
        q = deque([root])
        while q:
            floor = []
            for _ in range(len(q)):
                node = q.popleft()
                floor.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            ans.append(floor)
        return ans