题解 | #二叉树中和为某一值的路径#

方法一：递归DFS

• 使用DFS递归加回溯的方法。

  图解过程如下：

  

代码如下：

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        //DFS+回溯
        dfs(root,expectNumber);
        return ans;
    }
    void dfs(TreeNode* root,int expectNumber){
        if(root==nullptr)
            return;
        expectNumber-=root->val;
        //DFS，进入
        path.push_back(root->val);
        //满足条件的路径，值相等且当前为叶子节点。
        if(expectNumber==0&&root->left==nullptr&&root->right==nullptr){
            ans.push_back(path);
        }
        dfs(root->left,expectNumber);
        dfs(root->right,expectNumber);
        //回溯，恢复path。
        path.pop_back();
    }

};

复杂度分析：

时间复杂度：O(n^2)，取决于二叉树的形状。举例如下：

• 假设n/2的节点为链表状，n/2的节点为完全二叉树，每一个路径都是符合条件的，那么符合条件的路径数为n/4。每条路径上的节点数为（n/2+log(n+1/2))个，相乘时间复杂度为O(n^2)。

空间复杂度：O(n)。递归栈空间O(n)。

方法二：非递归DFS

• 相比于递归DFS,非递归的代码会相对复杂度更高，因为需要栈来存储节点和节点路径。
• 还有BFS的方法，相比于DFS，它会存储很多暂时用不到的数据，表现的效果不如DFS。

class Solution {
public:
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        vector<vector<int>> ans;
        vector<int> path;
        if(root==nullptr)
            return ans;
        //s是存储节点的栈，ps是存储对应节点路径的栈。
        stack<TreeNode*> s;
        stack<vector<int>> ps;
        s.push(root);
        path.push_back(root->val);
        ps.push(path);
        while(!s.empty()){
            TreeNode* cur=s.top();
            s.pop();
            vector<int> tmp=ps.top();
            ps.pop();
            //判断是否为所求路径
            if(cur->val==expectNumber&&cur->left==nullptr&&cur->right==nullptr)
                ans.push_back(tmp);
            //左右子节点是否存在，若存在，更新s和ps
            if(cur->right){
                vector<int> rtmp;
                for(int x:tmp)
                    rtmp.push_back(x);
                rtmp.push_back(cur->right->val);
                ps.push(rtmp);
                cur->right->val+=cur->val;
                s.push(cur->right);
            }
            if(cur->left){
                tmp.push_back(cur->left->val);
                ps.push(tmp);
                cur->left->val+=cur->val;
                s.push(cur->left);
            }
        }
        return ans;
    }
};

复杂度分析：

时间复杂度：O(n^2),同上
空间复杂度：O(n),用了一个存储路径和节点的栈。