【剑指Offer】（树）二叉树中和为某一值的路径

冷不防 2022-03-16 01:06 141阅读 0赞

**题目链接**：[https://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca?tpId=13&tqId=11177&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking][https_www.nowcoder.com_practice_b736e784e3e34731af99065031301bca_tpId_13_tqId_11177_tPage_2_rp_2_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]

#### 题目描述 ####

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

#### 解决方法 ####

/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/
    class Solution { 
        vector<vector<int>> res;
        vector<int> temp;
    public:
        vector<vector<int> > FindPath(TreeNode* root,int expectNumber) { 
            if(!root) return res;
            
            temp.push_back(root->val);
            //如果当前节点为叶子节点，且相加和刚好等于输入的整数，则该条路径满足条件
            if(!root->left && !root->right && root->val==expectNumber) res.push_back(temp);
            //如果不是叶子节点，则遍历它的子节点
            FindPath(root->left,expectNumber-root->val);
            FindPath(root->right,expectNumber-root->val);
            //返回父节点之前，在路径上删除当前节点
            if(!temp.empty()) temp.pop_back();
            
            return res;        
        }
    };

[https_www.nowcoder.com_practice_b736e784e3e34731af99065031301bca_tpId_13_tqId_11177_tPage_2_rp_2_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]: https://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca?tpId=13&tqId=11177&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking