方法一:递归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),取决于二叉树的形状。举例如下:
1

  • 假设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),用了一个存储路径和节点的栈。