Easy

题目描述

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

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

示例 1：

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

示例 2：

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

提示：

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

解题思路

这是一个典型的二叉树遍历问题，需要找到从根节点到所有叶子节点的路径。

主要思路：

  1. 深度优先搜索（DFS）+ 回溯：从根节点开始，递归遍历每个节点，维护当前路径。当到达叶子节点时，将当前路径加入结果集。回溯时需要移除当前节点，保证路径的正确性。

  2. 路径表示：可以用字符串直接拼接路径，也可以用数组维护路径然后最后拼接成字符串。

具体实现步骤：

  • 使用递归函数进行DFS遍历
  • 维护当前路径（可以是字符串或数组）
  • 当遇到叶子节点时，将路径添加到结果中
  • 递归处理左右子树
  • 回溯时恢复路径状态

推荐解法：使用字符串直接拼接的DFS方法，代码简洁且效率较高。时间复杂度为O(N)，其中N是节点数，每个节点访问一次。

代码实现

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        if (root == nullptr) return result;
        dfs(root, "", result);
        return result;
    }
    
private:
    void dfs(TreeNode* node, string path, vector<string>& result) {
        if (node == nullptr) return;
        
        path += to_string(node->val);
        
        // 叶子节点
        if (node->left == nullptr && node->right == nullptr) {
            result.push_back(path);
            return;
        }
        
        path += "->";
        dfs(node->left, path, result);
        dfs(node->right, path, result);
    }
};

class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        if not root:
            return []
        
        result = []
        
        def dfs(node, path):
            if not node:
                return
            
            path += str(node.val)
            
            # 叶子节点
            if not node.left and not node.right:
                result.append(path)
                return
            
            path += "->"
            dfs(node.left, path)
            dfs(node.right, path)
        
        dfs(root, "")
        return result

public class Solution {
    public IList<string> BinaryTreePaths(TreeNode root) {
        var result = new List<string>();
        if (root == null) return result;
        
        DFS(root, "", result);
        return result;
    }
    
    private void DFS(TreeNode node, string path, IList<string> result) {
        if (node == null) return;
        
        path += node.val.ToString();
        
        // 叶子节点
        if (node.left == null && node.right == null) {
            result.Add(path);
            return;
        }
        
        path += "->";
        DFS(node.left, path, result);
        DFS(node.right, path, result);
    }
}

var binaryTreePaths = function(root) {
    if (!root) return [];
    
    const result = [];
    
    function dfs(node, path) {
        if (!node) return;
        
        path += node.val.toString();
        
        // 叶子节点
        if (!node.left && !node.right) {
            result.push(path);
            return;
        }
        
        path += "->";
        dfs(node.left, path);
        dfs(node.right, path);
    }
    
    dfs(root, "");
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(N)N为树中节点数，每个节点访问一次
空间复杂度O(N)递归栈的深度最坏情况下为O(N)，结果存储空间也为O(N)

相关题目