当前位置：首页 > article >正文

【LeetCode 刷题】二叉树-深度优先遍历

article 2025/1/24 12:23:23

此博客为《代码随想录》二叉树章节的学习笔记，主要内容为二叉树的深度优先遍历相关的题目解析。

文章目录

144. 二叉树的前序遍历
递归法
迭代法

94. 二叉树的中序遍历
递归法
迭代法

145. 二叉树的后序遍历
递归法
迭代法

144. 二叉树的前序遍历

题目链接

递归法

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

可以将判断节点为空的逻辑放在递归函数最开始，从而避免判断根节点以及左右子节点为空的逻辑

迭代法

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        if root is None:
            return res
        stack = [root]
        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

若栈不为空，每次从栈中弹出一个节点，并处理该节点，之后依次将右、左节点压入栈中（先右后左，由于栈的处理顺序是反的）
代码最开始先判断跟节点是否为空；之后的遍历过程中，先判断节点是否存在右、左子节点，再压入栈中

94. 二叉树的中序遍历

题目链接

递归法

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

迭代法

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

节点的访问顺序的处理顺序不一致（只有前序遍历是一致的），需要借助指针 cur 来访问节点，栈来处理节点
将左节点依次入栈，直到为空，弹出栈顶元素进行处理，之后切换到右节点重复上述操作

145. 二叉树的后序遍历

题目链接

递归法

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

迭代法

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