二叉树中路径问题

Posted on | In

二叉树中和为某一值的路径

题目链接：https://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca?tpId=13&tqId=11177&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目来源：剑指Offer

题目描述

输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。

路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

时间限制：1秒 空间限制：32768K 热度指数：167478

解题思路：

**带记忆的 DFS**, 递归

提交记录：

1. 递归结束条件始终有问题；

    注意路径终点是叶节点，而不是子节点

​ 

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

vector<vector<int>> res;

vector<int> buf;

    

    

void dfs(TreeNode *root, int expectNumber){

    

    buf.push_back(root->val);

    

    if(!root->left && !root->right && expectNumber == root->val)

        res.push_back(buf);

        

    //或前加进入判断,空则不进仅走有路的情况，更像图的深搜，终点路径为叶结点

    if(root->left)

        dfs(root->left, expectNumber - root->val);

    if(root->right)

        dfs(root->right, expectNumber - root->val);

        

    buf.pop_back();

}

vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {

    if(root == NULL) return res;

    dfs(root, expectNumber);

    return res;

}
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

vector<vector<int>> res;

vector<int> buf;



vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {

    if(root == NULL) return;



    expectNumber = expectNumber - root->val;

    

    buf.push_back(root->val);

    

    if (expectNumber == 0 && root->left == NULL && root->right == NULL) {

        res.push_back(buf);

    }

    

    ////不加if(root->right)但前要加为空返回,多进一层

  

    FindPath(root->left, expectNumber);

    FindPath(root->right, expectNumber);

    

    buf.pop_back();

    

    return res;

}

LeetCode 129. Sum Root to Leaf Numbers

题目链接：(https://leetcode.com/problems/sum-root-to-leaf-numbers/)

解法1:先序遍历的思想(根左右)+数字求和(每一层都比上层和*10+当前根节点的值)

PS:和求二叉树深度等题及其类似，满足叶子结点条件返回某值

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

int preOrder(TreeNode *root, int sum){

    if(root == NULL)

        return 0;

        

    sum = sum*10 + root->val;

    

    if(root->left == NULL && root->right == NULL)

        return sum;

        

    int sum1 = preOrder(root->left, sum);

    int sum2 = preOrder(root->right, sum);

    

    return sum1 + sum2;

    }

int sumNumbers(TreeNode* root) {

    int sum = preOrder(root, sum);

    return sum;

    }

更详细版:从根结点开始，当每访问到一个结点，我们把该结点添加到路径上，并”累加”

该结点的值，这里”累加”的含义指的是按照题目的要求组成相应的数字即”左移”后相加。

如果该结点为叶结点，那么一条路径搜索完成，将当前所得结果累加。如果当前不是叶子

结点，则继续访问它 的子结点。当前结点访问结束后，递归函数将自动回到它的父结点。

因此我们在函数退出之前要在路径上”删除”当前结点，做法就是将当前路径值/10，以确

保返回父结点时路径刚好是从根结点到父结点的路径。我们不难看出保存路径的数据结构

实际上是一个栈，因为路径要与递归调用状态一致，而递归调用的本质就是一个压栈和出

栈的过程。

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
51
52
53
54
55
56

class Solution {

public:

    void sumNumbersCore(TreeNode *root, int &pathNum, int &sum) {

        if(root){

            pathNum = pathNum * 10 + root->val;

            //如果是叶子节点，一条路径搜索完成，累加到sum

            if(!root->left && !root->right){

                sum += pathNum;              

            }

            //如果不是叶子节点，则遍历它的子结点

            else{

                if(root->left)

                    sumNumbersCore(root->left, pathNum, sum);

                if(root->right)

                    sumNumbersCore(root->right, pathNum, sum);

            }

            //返回父结点之前，路径上“删除”当前节点

            pathNum /= 10;                    

        }

    }

     

    int sumNumbers(TreeNode *root) {

        int pathNum = 0;

        int sum = 0;

        sumNumbersCore(root, pathNum, sum);

        return sum;

    }

};

解法2:路径问题一般用后续遍历，遍历到当前结点时栈里即为路径结点，再求和即可

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

int sumOfVector(vector<int> sum){

    int decimal = 1;

    int res = 0;

    for(int i = 0; i < sum.size(); ++i){

        res *= 10;

        res +=  sum[i];

    }

    return res;

}

int sumNumbers(TreeNode *root){

    TreeNode* stk[1000] = {0};

    int top = -1;

    TreeNode *cur = root, *f_last = NULL;

    vector<int> res;

    long long totalSum = 0;

    while(cur || top != -1){

        if(cur){

            stk[++top] = cur;

            cur = cur->left;

        }

        else{

            cur = stk[top];

            if(cur->right && f_last != cur->right){

                cur = cur->right;

            }

            else{

                f_last = cur;

                if(cur->left == NULL && cur->right == NULL){

                    vector<int> sum;

                    for(int i = 0; i <= top; ++i)

                        sum.push_back(stk[i]->val);

                    res.push_back(sumOfVector(sum));

                }

                top--;

                cur = NULL;

            }

        }

    }

    for (int i = 0; i < res.size(); ++i)

        totalSum += res[i];

    return totalSum;

}