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

剑指offer BTree

Created At : 2019-12-26 23:12

Count:379 Views 👀 :

Comment:

二叉树中和为某一值的路径
1. 思路分析

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

输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。
路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
(注意: 在返回值的list中，数组长度大的数组靠前)

思路分析

深度优先搜索，保存路径（有多少个叶子就有多少个路径），前序遍历即可
疑问：没有保证最长路径靠前呀？？？？傻子没见到是深度优先吗？

/*
二叉树结构
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:

    vector<vector<int>> ans;// 返回结果
    vector<int> target;// 阶段结果
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        // 递归退出条件
        if (root == nullptr) { // 空节点，不可能有路径，直接返回
            return ans;
        }
        // 节点处理
        target.push_back(root->val);
        // 判断是否找到目标值，是的话，路径加入到目标数组中
        if ((root->val == expectNumber) && root->left == nullptr && root->right == nullptr){ // 找到一条路径
            ans.push_back(target);
        } 
        // 递归遍历左右子树，更新目标值，因为ans是全局变量，返回值可不管
        FindPath(root->left,expectNumber-root->val);
        FindPath(root->right,expectNumber-root->val);
        // 回溯，与函数递归保持一致
        if (!target.empty()) {// 后退一格
            target.pop_back();
        }
        return ans;
    }
};

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com