LeetCode 0257. 二叉树的所有路径

【LetMeFly】257.二叉树的所有路径

力扣题目链接：https://leetcode.cn/problems/binary-tree-paths/

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

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

 

示例 1：

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

示例 2：

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

 

提示：

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

方法一：DFS

深搜遍历二叉树，在遍历的过程中将所经过路径记录下来。如果遇到了叶子节点，就把当前路径加入答案中。

• 时间复杂度$O(n^2)$，其中$n$是二叉树节点个数
• 空间复杂度$O(n^2)$

AC代码

C++

class Solution {
private:
    vector<string> ans;

    // void doNothing() {
    //     return;
    // }

    void dfs(TreeNode* root, string now) {
        if (!root->left && !root->right) {
            ans.push_back(now);
        }
        if (root->left) {
            dfs(root->left, now + "->" + to_string(root->left->val));
        }
        if (root->right) {
            dfs(root->right, now + "->" + to_string(root->right->val));
        }
    }
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        dfs(root, to_string(root->val));
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/126813644