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

LeetCode 257.二叉树的所有路径

article 2025/2/7 3:39:44

题目描述

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

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

示例 1：

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

示例 2：

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

提示：

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

思路

本题要求从根节点到叶子的路径，所以需要前序遍历，这样才方便让父节点指向孩子节点，找到对应的路径。

递归三部曲：

确定递归函数的参数和返回值。要传入根节点，记录每一条路径的path，和存放结果集的result，这里递归不需要返回值。
确定终止条件。本题没有必要遍历到空节点才结束，只需要遍历到叶子结点就可以结束了。当cur不为空，且其左右孩子都为空的时候，就找到叶子节点了。
确定单层递归的逻辑。因为是前序遍历，需要先处理中间节点，中间节点就是我们要记录路径上的节点，先放进path中。然后是递归和回溯的过程，递归时需要先判断cur是否为空，如果为空就不进行下一层递归了。递归之后就要回溯，因为path不能一直加入节点，它还要删节点，然后才能加入新的节点。

代码

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:
    // 递归法
    // path存放路径,result存放结果集
    void traversal(TreeNode* n,vector<int>& path,vector<string>& result){
        // 中
        path.push_back(n->val);
        // 终止条件，到达叶子节点
        if(n->left==NULL && n->right==NULL){
            string sPath;
            for (int i = 0; i < path.size() - 1; i++) {
                sPath += to_string(path[i]);
                sPath += "->";
            }
            sPath += to_string(path[path.size() - 1]);
            result.push_back(sPath);
            return; 
        }
        // 左
        if(n->left){
            traversal(n->left,path,result);
            path.pop_back(); // 回溯
        }
        // 右
        if(n->right){
            traversal(n->right,path,result);
            path.pop_back(); // 回溯
        }
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<int> path;
        vector<string> result;
        if(root==NULL) return result;
        traversal(root,path,result);
        return result;
    }
};

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 traversal(self, cur, path, result):
        path.append(cur.val)  # 中
        if not cur.left and not cur.right:  # 到达叶子节点
            sPath = '->'.join(map(str, path))
            result.append(sPath)
            return
        if cur.left:  # 左
            self.traversal(cur.left, path, result)
            path.pop()  # 回溯
        if cur.right:  # 右
            self.traversal(cur.right, path, result)
            path.pop()  # 回溯
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        result = []
        path = []
        if not root:
            return result
        self.traversal(root, path, result)
        return result