题目描述 牛客网

• 输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径
• 路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径

题目解读

• 剑指Offer 182

代码

class Solution {
public:
    void FindPathCore(TreeNode *root, int expectNumber, int currentNumber, vector<vector<int> >& pp, vector<int>& pp_core){
        pp_core.push_back(root->val);
        currentNumber += root->val;

        bool isLeaf = !root->left && !root->right;
        // 若到达叶子节点，且该路径为给定值，则找到一条路径
        if(currentNumber == expectNumber && isLeaf){
            pp.push_back(pp_core);
        }
        
        // 若到达叶子节点，叶子节点的左右孩子均为空，则下面这两个if都不会执行
        if(root -> left){
            FindPathCore(root->left, expectNumber, currentNumber, pp, pp_core);
        }

        if(root -> right){
            FindPathCore(root->right, expectNumber, currentNumber, pp, pp_core);
        }
        // 执行到这里表示要递归往上走了
        pp_core.pop_back();
        // currentNumber -= root->val; 注意这句话在此没用，这是递归，不是指针更不是引用，递归中下一层数值影响不到上一层
    }

    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        vector<vector<int> > pp;
        vector<int> pp_core;
        int currentNumber = 0;

        if(root == NULL){
            return pp;
        }

        FindPathCore(root, expectNumber, currentNumber, pp, pp_core);
        return pp;
    }
};

总结展望

• 一般做二叉树类型的题目，都是用的递归！