剑指offer

原题链接

• • 思路
  • C++代码

首先：要求二叉树的每个节点上的值，一定需要遍历二叉树，并且要先访问根节点。在二叉树的三种遍历方式中先访问根节点为二叉树的前序遍历。题目要求打印路径，从根节点到最后的叶节点才是一条路径。

其次考虑，题干要求返回的是二叉树节点路径，所以我们需要定义一个空间来存放路径。

再考虑查找的过程，以上题为例子

根据上表分析储存路径的数据结构为后进先出的形式，所以用栈来存储。

返回形式
题目最后要求以二维数组的形式返回路径，所以我们用数组来存储路径，只要每次尾插数据，尾删数据，数组也可以看作为栈，当数组路径和与设置的相同时尾插到这个二维数组上。并且因为要以递归的形式来遍历二叉树，所以我们把二维数组定义为全局的形式，避免多次递归带来的性能损耗

我们在做这种递归的题的时候要想清楚三步

1.递归出口。2.子步骤要执行什么。3.递归条件与路径

1.递归出口：左右子树为空时(叶子节点)，这时还要判断路径和与设定值是否相同，结束后还要退回上一个节点，所以还要把这个节点踢出数组。

2.子步骤：每次递归到这个节点时要把这个节点的值加到记录路径和的变量中，同时还要把这个节点的数字尾插到数组上

3.递归条件与路径：二叉树的先序遍历，递归时当左树不为空时先递归左树。在左树为空后再递归右树

之后再以合理的方式将这三步组织起来

class Solution {
public:
    vector>ret;
    vector > FindPath(TreeNode* root,int expectNumber) {
        if(root==nullptr)
            return ret;
        int SumStack=0;//记录路径的和
        vectorPath;//存放路径
        _FindPath(root,expectNumber,Path,SumStack);
        return ret;
    }
private:
    void _FindPath(TreeNode*root,int expectNumber,vector&Path,int SumStack)
    {
        SumStack=SumStack+root->val;//子步骤
        Path.push_back(root->val);
        if(root->left)//递归路径与递归条件
        {
            _FindPath(root->left,expectNumber,Path,SumStack);
        }
        if(root->right)
        {
            _FindPath(root->right,expectNumber,Path,SumStack);
        }
 //递归出口，在叶子节点要和规定值做对比，相同时尾插到全局的二维数组中
        if(SumStack==expectNumber&&root->left==nullptr&&root->right==nullptr)//叶子节点且有相等的值
        {
            ret.push_back(Path);
        }
        Path.pop_back();
    }
};