题目意思

  • 这个题目的意思和JZ24的题目几乎一模一样，就是对于从根节点到叶子节点的所组成的路径中。选择路径中的所有的权值之和等于给定的某一个数的路径。并且将他们返回。

  • 前置知识。这个题目我用的分别是DFS和BFS进行处理的。其中DFS用了一个回溯的方法进行处理。
    回溯法是一个DFS的技巧，就是当我们DFS遍历某一个子节点的时候，我们还需要回来遍历另一个子节点，为了消除之前遍历的时候的影响，我们需要将状态进行复原。结合下面的图理解回溯。

图片说明

思路分析

  • 好了我们知道了回溯和搜索的思想之后，这个题目就可以开始写了。

解法一 DFS

  • 我们从根节点向下进行搜索。同时我们开一个二维的动态数组记录我们最后的答案。然后我们开一个一维的vector作为中间变量存储中间路径。
    • 递归的边界： 当我们遍历到某一个节点没有左右子节点的时候。我们对当前存储的路径进行求和，判断是否满足题目给定的数字。
    • 递归的前进段，我们判断是否可以向左或者向右进行递归。然后先将结点的值存入路径进行向下递归，然后回溯。
  • 代码如下
    • 进行DFS的时候需要遍历每一个点，时间复杂度为O(n）
    • 需要存储所有的结点的信息，空间复杂度为O(n) 
/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return int整型vector<vector<>>
     */
    vector<vector<int>> ans; // 将这个变量设为全局变量，减少参数的传递
    void DFS(TreeNode* now,vector<int> path,int sum){
        // 如果这个节点没有了左右子节点，就说明这个节点是叶子节点
        if(now->left==NULL&&now->right==NULL){
            int s=0;
            // 计算所有的路径的和
            for(auto x:path){
                s+=x;
            }
            // 如果路径的和满足题目给定的数字
            if(s==sum){
                ans.push_back(path);
            }
            return;
        }
        // 单独遍历左边的子节点
        if(now->left){
            path.push_back(now->left->val);
            DFS(now->left,path,sum);
            // 回溯
            path.pop_back();
        }
        // 单独遍历右边的子节点
        if(now->right){
            path.push_back(now->right->val);
            DFS(now->right,path,sum);
            // 回溯
            path.pop_back();
        }
    }
    vector<vector<int> > pathSum(TreeNode* root, int sum) {
        // write code here
        // 判断根节点为空的情况
        if(!root){
            return ans;
        }
        vector<int> path;
        path.push_back(root->val);
        DFS(root,path,sum);
        return ans;
    }
};

解法二 BFS

  • 对于DFS，如果树过深的话可能会存在爆栈的风险，所以我们一般也要掌握BFS的写法，其实思想还是搜索和回溯的思想。只是写法的不一样。
  • 代码如下
    • 进行BFS的时候需要遍历所有的结点，并且每个结点只会被遍历一遍，时间复杂度为O(n）
    • 我们需要存储所有的结点的信息，空间复杂度为O(n) 
/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > ans;
    vector<vector<int> > pathSum(TreeNode* root, int sum) {
        // write code here
        if(!root){
            return ans;
        }

        // 用来存储遍历过的结点
        vector<TreeNode*> node;
        // 用来存储中间路径
        vector<int> s;
        int SUM=0;
        TreeNode* now=root;
        TreeNode* pre;
        while(now||!node.empty()){
            // 一直往左边进行遍历，知道到达最左端
            while(now){
                SUM+=now->val;
                node.push_back(now);
                s.push_back(now->val);
                now=now->left;
            }
            // 这步是回到上一个节点
            now=node.back();
            // 往右边走
            if(now->right&&now->right!=pre){
                now=now->right;
            }else{
                pre=now;
                // 这个是一个叶子节点
                if(!now->right&&!now->left){
                    if(SUM==sum){
                        ans.push_back(s);
                    }
                }
                // 回溯
                SUM=SUM-now->val;
                node.pop_back();
                s.pop_back();
                now=NULL;
            }
        }
        return ans;
    }
};