Path Question In Tree

发表于 | 分类于

Path Question In Tree

题目描述1：

给定一棵树的头结点和一个目标值；判断是否树中存在一条从根到叶的路径，其路径上节点和的值为目标值。

例子：

这题是leetcode上的题目，可以看这上面的题目描述.

解题思路：

主要的思路还是递归来解决这道题目。我们在不断的遍历树的过程中，对sum值进行改变，即减去当前遍历节点上的值；如果遇到了当前是叶节点，并且其值和当前的目标值相同，就直接返回true.

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if (!root)
            return false;
            //如果是空节点，返回false
        if (root->left == NULL && root->right == NULL)
            return root->val == sum ? true : false;
            //如果是叶节点，判断和当前sum的关系
        if (root){
            if (hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val))
                return true;
        }
        //如果不是叶节点，就递归遍历左右节点，只要有一个是true即可
        return false;
        
    }
};

题目描述2：

给定一棵树的头结点和一个目标值；找到树中所有从根到叶节点和为目标值的情况并返回。

例子：

leetcode上的题目描述

解题思路：

本题的思路在与使用回溯的方法；但是需要注意的点是什么时候回溯。我们用一个vector保存当前路径的节点；用一个vector保存每次符合条件后保存路径。

代码如下：

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<int> list;//保存当前路径
        vector<vector<int>> res;//保存符合条件的路径
        findPath(root, list, sum, res);
        return res;
    }
    void findPath(TreeNode* head, vector<int>& list, int target, vector<vector<int>>& res){
        if (!head) return;//如果是空节点直接返回
        
        list.push_back(head->val);//将当前节点保存到路径中
        if (!head->left && !head->right && head->val == target)
            res.push_back(list);
            //如果是叶节点，并且符合条件，将其保存到结果中
        findPath(head->left, list, target - head->val, res);
        findPath(head->right, list, target- head->val, res);
        list.pop_back();
        //如果是叶节点，不管是不是符合条件都会进入这个流程；但是叶节点的左右都是空，直接返回，最后一句话进行了回溯
    }
};

题目描述3:

给定一棵树的头节点和一个目标值，要求返回树中任意从父节点到子节点路径和为目标值的个数。

例子:

这题也是leetcode上的题目，详情可见此处.

解题思路：

当然这题的思路依旧是递归的方式；但是有不同的是，我们需要判断在遍历到当前节点的时候，其遍历的路径上的子路径是否存在符合条件的情况。所以我们主要是用一个vector保存了遍历到当前节点的路径上的累加和；这样我们就可以通过遍历累加和数组来判断当前路径上是否存在符合要求的路径。

代码如下:

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
class Solution {
public:
    int pathSum(TreeNode* root, int sum) {
        if (!root) return 0;
        //空节点直接返回0
        vector<int> path{0};
        //先在路径和数组中放入0，用来表示从根节点开始的情况
        int res = 0;
        //保存符合条件的情况个数
        helper(root, path, sum, res);
        return res;
    }
    void helper(TreeNode* root, vector<int> &path, int sum, int &res){
        if (!root) return;
        //如果是空节点直接返回即可
        path.push_back(root->val + path[path.size() - 1]);
        //将当前节点的值和上一个节点的路径和保存到路径和数组中
        int cur = path.back();
        //以当前节点的路径和为标杆
        for (int i = path.size() - 2; i >= 0; i--){
            if (cur - path[i] == sum) res++;
        }
        //遍历数组中是否存在符合条件的情况
        helper(root->left, path, sum, res);
        helper(root->right, path, sum, res);
        //分别遍历左右节点
        path.pop_back();
        //最后记得回溯一步
    }
};

题目描述4：

给定一棵树的头结点，从树的头结点到根节点的每一条路径都代表了一个数，要求返回所有路径代表的数的和。

这道题的具体描述可以看LeetCode129.

解题思路：

主要解题思路也是很直接，我们不断的往树的深度遍历，主要用一个变量来记录每条路径上所代表的数，用一个变量记录所有路径的总和即可。

代码如下：

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int sumNumbers(TreeNode* root) {
        int res = 0;
        path(root, 0, res);
        return res;
    }
    void path(TreeNode* root, int cur, int& res){
        if (!root) return;
        if (!root->left && !root->right){
            res = res + cur * 10 + root->val;
            return;
            // 如果是叶节点，我们就将当前路径的数累加
        }
        path(root->left, cur * 10 + root->val, res);
        path(root->right, cur * 10 + root->val, res);
        //分别继续遍历左右节点的路径，用乘以10来代表路径上的10进制数
    }
};

题目描述5：

给定一棵树的头结点，要求返回树中的每一条路径表示，例如1->2->3等。
依旧是LeetCode的题目LeetCode257。具体描述可以看这里。解题思路不再赘述。

代码如下：

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        string path = "";
        //代表某条路径
        vector<string> res;
        //保存全部路径
        helper(root, res, path);
        return res;
    }
    void helper(TreeNode* root, vector<string> &vec, string path){
        if (!root){
            return;
        }
        if (!root->left && !root->right){
            vec.push_back(path + to_string(root->val));
            return;
            //碰到叶节点保存结果并返回
        }
        helper(root->left, vec, path + to_string(root->val) + "->");
        helper(root->right, vec, path + to_string(root->val) + "->");
        //继续遍历左右节点，注意"->"加在此处，便于处理叶节点的情况
    }
};

题目描述6:

给定一棵树的头结点，要求返回树的每条路径上各自的最大值。
具体题目描述可以看LeetCode515.
这边代码的解法使用的是按层遍历的方式，找到每一条路径上的数然后保存排序找到最大值；当然也可以直接遍历。

代码如下：

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<vector<int>> res;
        vector<int> result;
        if (!root) return result;
        queue<TreeNode*> cur;
        queue<TreeNode*> next;
        cur.push(root);
        while(!cur.empty()){
            vector<int> row;
            while(!cur.empty()){
                TreeNode* front = cur.front();
                cur.pop();
                row.push_back(front->val);
                if (front->left) next.push(front->left);
                if (front->right) next.push(front->right);
            }
            res.push_back(row);
            queue<TreeNode*> tmp = cur;
            cur = next;
            next = tmp;
        }
        for (auto vec: res){
            sort(vec.begin(), vec.end());
            result.push_back(vec[vec.size() - 1]);
        }
        return result;
        
    }
};