0%

二叉树的所有路径

发表于 分类于 ， Disqus：

给定一个二叉树，返回从根节点到叶节点的所有路径。

例如，给定以下二叉树:

1
2
3
4
5
 1
 /   \
2     3
 \
  5

所有根到叶路径是:

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

解答：

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
vector<string> binaryTreePaths(TreeNode* root) {
    vector<vector<int>> collection;
    vector<string> res;
    vector<int> chain;
    binaryTreePathsRecur(root, collection, chain);
    for (auto& i : collection) {
        res.push_back(convertVectorToString(i));
    }
    return res;
}

void binaryTreePathsRecur(TreeNode* root, vector<vector<int>>& collection, vector<int>& chain) {
    if (!root) {
        return;
    }
    if (!root->left && !root->right) {
        vector<int> copy(chain);
        copy.push_back(root->val);
        collection.push_back(copy);
        return;
    }
    chain.push_back(root->val);
    binaryTreePathsRecur(root->left, collection, chain);
    binaryTreePathsRecur(root->right, collection, chain);
    chain.pop_back();
}

string convertVectorToString(vector<int> nums) {
    string res;
    for (auto i = nums.begin(); i != nums.end(); i++) {
        if (i == nums.end() - 1) {
            res += to_string(*i);
        }
        else {
            res += to_string(*i) + "->";
        }
    }
    return res;
}