257. 二叉树的所有路径

link

给你一个二叉树的根节点 root ，按任意顺序，返回所有从根节点到叶子节点的路径。叶子节点是指没有子节点的节点。

思路

要从根节点出发，记录路径，一直走到叶子节点，把这条路径记录下来。必须先访问根节点，所以只能用前序遍历。涉及到回溯，因为我们要把路径记录下来，需要回溯来回退一个路径再进入另一个路径。

递归法(DFS)

逻辑

把当前节点的值加入路径中
如果是叶子节点，就把路径加入结果集
否则继续递归左右子树
回溯时，把路径中当前节点的值弹出，回退到上一步

class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        res = []
        path = []

        def treverse(node):
            path.append(str(node.val))

            if node.left == None and node.right == None:
                res.append("->".join(path))
            if node.left:
                treverse(node.left)
            if node.right:
                treverse(node.right)
            
            path.pop()
        
        if root !=None:
            treverse(root)
        return res

BFS

层序遍历，队列中直接存储当前节点以及其对应的路径

class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        res = []
        que = deque()
        if root != None:
            que.append((root, [str(root.val)]))
        while que:
            cur, path = que.popleft()
            if cur.left == None and cur.right == None:
                res.append("->".join(path))
            if cur.left:
                que.append((cur.left, path + [str(cur.left.val)]))
            if cur.right:
                que.append((cur.right, path + [str(cur.right.val)]))
        return res

注意，上述代码中，入队时不能使用 append，因为如果左右节点都存在，那么会错误添加元素

404.左叶子之和

link

输入: root = [3,9,20,null,null,15,7]
输出: 24
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

思路

dfs 遍历该树，遇到左节点为叶子节点就记录其数值，否则遍历其子树。注意这里写成了 res = [0]，不写 res=0 是因为在函数内部对某个变量赋值（如 res += …），Python 会默认把这个变量当作函数的局部变量。

class Solution:
    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        res = [0]  # ✅ 使用 list 包装成可变对象

        def dfs(node):
            if node.left:
                # 如果左孩子是叶子节点才加
                if not node.left.left and not node.left.right:
                    res[0] += node.left.val
                else:
                    dfs(node.left)
            if node.right:
                dfs(node.right)

        if root:
            dfs(root)

        return res[0]

513.找树左下角的值

link

给定一个二叉树的根节点 root，请找出该二叉树的最底层最左边节点的值。

思路

层序遍历，取最后一层的第一个结果

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        res = []
        que = deque()
        que.append(root)

        while que:
            cur_level = []
            for _ in range(len(que)):
                
                cur = que.popleft()

                cur_level.append(cur.val)
                if cur.left:
                    que.append(cur.left)
                if cur.right:
                    que.append(cur.right)        
                    
            res.append(cur_level)
        
        return res[-1][0]

112. 路径总和

link

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

思路

类似于 257. 二叉树的所有路径，只是当访问到叶子节点时，就计算路径和，判断是否满足条件。使用 BFS 较为简单，可以更好控制返回时机。

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        que = deque()

        if root:
            que.append((root, [root.val]))
        while que:

            cur, path = que.popleft()
            if cur.left == None and cur.right == None:
                s = sum(path)
                if s == targetSum:
                    return True
            if cur.left:
                que.append((cur.left, path + [cur.left.val]))
            
            if cur.right:
                que.append((cur.right, path + [cur.right.val]))
        
        return False