LeetCode: 257. Binary Tree Paths

发表于 | 分类于

题目描述

Given a binary tree, return all root-to-leaf paths.

Note: A leaf is a node with no children.

Example:

1
2
3
4
5
6
7
8
9
10
11
Input:

   1
 /   \
2     3
 \
  5

Output: ["1->2->5", "1->3"]

Explanation: All root-to-leaf paths are: 1->2->5, 1->3

使用DFS来找所有的path后，打印即可。

代码实现

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
private:
    vector<vector<int>> _paths;
    void findPath(TreeNode* root, vector<int>& path) {
        if (root == NULL) {
            return;
        }

        path.push_back(root->val);


        if (root->left != NULL){
            findPath(root->left, path);
            path.pop_back();
        }

        if (root->right != NULL){
            findPath(root->right, path);
            path.pop_back();
        }

        if (root->left == NULL && root->right == NULL){
            _paths.push_back(path);
        }
    }

    vector<string> printPath() {
        vector<string> result;
        for (auto i: _paths) {
            string s;
            for (auto j: i) {
                if (s == "") {
                    s += to_string(j);
                } else {
                    s += "->";
                    s += to_string(j);
                }
            }
            result.push_back(s);
        }
        return result;
    }

public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<int> path(0);
        findPath(root, path);
        return printPath();
    }
};