江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode第257题：二叉树的所有路径

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

题目描述

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

叶子节点是指没有子节点的节点。

难度

简单

题目链接

点击在LeetCode中查看题目

示例

示例 1：

示例1图片

输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]

示例 2：

输入：root = [1]
输出：["1"]

提示

  • 树中节点的数目在范围 [1, 100] 内
  • -100 <= Node.val <= 100

解题思路

方法一：深度优先搜索（递归）

这是一个典型的深度优先搜索（DFS）问题。我们需要遍历整个二叉树，找出所有从根节点到叶子节点的路径。

关键点

  • 递归遍历二叉树
  • 用字符串记录当前路径
  • 当遇到叶子节点时，将完整路径添加到结果列表中
  • 处理路径格式，使用 “->” 连接节点值

具体步骤

  1. 定义一个递归函数，参数包括当前节点和当前路径字符串
  2. 如果当前节点为叶子节点（左右子节点都为空），则将当前路径添加到结果列表中
  3. 如果当前节点有左子节点，递归处理左子节点
  4. 如果当前节点有右子节点，递归处理右子节点
  5. 返回结果列表

复杂度分析

  • 时间复杂度：O(n)，其中 n 是树中节点的数量。每个节点在递归中只被访问一次。
  • 空间复杂度：O(h)，其中 h 是树的高度。空间复杂度主要取决于递归调用的栈空间，最坏情况下，树呈现链状，高度为 n，空间复杂度为 O(n)。

方法二：广度优先搜索（迭代）

除了递归，我们也可以使用广度优先搜索（BFS）来解决这个问题。通过队列存储节点和对应的路径。

关键点

  • 使用队列进行层序遍历
  • 同时存储节点和对应的路径
  • 当遇到叶子节点时，将完整路径添加到结果列表中

具体步骤

  1. 创建一个队列，初始时将根节点和根节点的值（作为字符串）入队
  2. 当队列不为空时，出队一个节点和对应的路径
  3. 如果当前节点是叶子节点，将当前路径添加到结果列表中
  4. 如果当前节点有左子节点，将左子节点和更新后的路径入队
  5. 如果当前节点有右子节点，将右子节点和更新后的路径入队
  6. 继续步骤2，直到队列为空
  7. 返回结果列表

复杂度分析

  • 时间复杂度：O(n)，其中 n 是树中节点的数量。每个节点只被访问一次。
  • 空间复杂度：O(n)，队列中最多存储 n 个节点及其路径。

图解思路

递归过程示例

以示例1为例，root = [1,2,3,null,5]：

节点 当前路径 操作 结果集
1 “1” 递归左子节点(2) []
2 “1->2” 递归左子节点(null)，递归右子节点(5) []
5 “1->2->5” 是叶子节点，添加路径 [“1->2->5”]
3 “1->3” 是叶子节点，添加路径 [“1->2->5”, “1->3”]

函数调用栈分析

调用层级 当前节点 当前路径 返回值
1 根节点(1) “1” [“1->2->5”, “1->3”]
2 左子节点(2) “1->2” [“1->2->5”]
3 右子节点(5) “1->2->5” [“1->2->5”]
2 右子节点(3) “1->3” [“1->3”]

代码实现

C# 实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public IList<string> BinaryTreePaths(TreeNode root) {
        List<string> paths = new List<string>();
        if (root == null) return paths;
        
        DFS(root, "", paths);
        return paths;
    }
    
    private void DFS(TreeNode node, string path, List<string> paths) {
        // 更新当前路径
        path += node.val;
        
        // 如果是叶子节点，添加到结果列表
        if (node.left == null && node.right == null) {
            paths.Add(path);
            return;
        }
        
        // 继续递归左右子树
        if (node.left != null) {
            DFS(node.left, path + "->", paths);
        }
        
        if (node.right != null) {
            DFS(node.right, path + "->", paths);
        }
    }
}

Python 实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        if not root:
            return []
        
        paths = []
        
        def dfs(node, path):
            # 更新当前路径
            path += str(node.val)
            
            # 如果是叶子节点，添加到结果列表
            if not node.left and not node.right:
                paths.append(path)
                return
            
            # 继续递归左右子树
            if node.left:
                dfs(node.left, path + "->")
            
            if node.right:
                dfs(node.right, path + "->")
        
        dfs(root, "")
        return paths

C++ 实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> paths;
        if (root == nullptr) return paths;
        
        dfs(root, "", paths);
        return paths;
    }
    
private:
    void dfs(TreeNode* node, string path, vector<string>& paths) {
        // 更新当前路径
        path += to_string(node->val);
        
        // 如果是叶子节点，添加到结果列表
        if (node->left == nullptr && node->right == nullptr) {
            paths.push_back(path);
            return;
        }
        
        // 继续递归左右子树
        if (node->left != nullptr) {
            dfs(node->left, path + "->", paths);
        }
        
        if (node->right != nullptr) {
            dfs(node->right, path + "->", paths);
        }
    }
};

执行结果

C# 实现

  • 执行用时：252 ms
  • 内存消耗：42.1 MB

Python 实现

  • 执行用时：36 ms
  • 内存消耗：15.2 MB

C++ 实现

  • 执行用时：4 ms
  • 内存消耗：13.8 MB

性能对比

语言 执行用时 内存消耗 特点
C# 252 ms 42.1 MB 代码结构清晰，但性能较差
Python 36 ms 15.2 MB 实现简洁，性能适中
C++ 4 ms 13.8 MB 性能最佳，内存占用最小

代码亮点

  1. 🎯 递归实现简洁明了，逻辑清晰
  2. 💡 通过字符串拼接记录路径，避免了使用额外的数据结构
  3. 🔍 处理叶子节点的判断条件准确无误
  4. 🎨 代码结构良好，易于理解和维护

常见错误分析

  1. 🚫 忘记处理根节点为空的边界情况
  2. 🚫 路径拼接格式错误，如忘记添加 “->” 分隔符
  3. 🚫 判断叶子节点的条件错误，如只检查了左子节点为空
  4. 🚫 递归终止条件不正确，导致无法获取完整路径

解法对比

解法 时间复杂度 空间复杂度 优点 缺点
深度优先搜索（递归） O(n) O(h) 实现简单，代码清晰 在树很深时可能导致栈溢出
广度优先搜索（迭代） O(n) O(n) 避免递归栈溢出问题 实现较复杂，需要额外存储路径
深度优先搜索（迭代） O(n) O(n) 避免递归栈溢出问题 实现最复杂，需要使用栈来模拟递归

相关题目