题意分析

  • 给你一棵二叉树，需要求出这棵二叉树从根节点到叶子节点形成的连续的路径中路径和等于给定的数字的情况，并且按照字典序输出。

  • 样例解释

图片说明
对于样例一，我们发现一共存在三条路径，分别为[10,5,4],[10,5,7]和[10,12].所以我们样例就很好理解了。

思路分析

DFS+回溯法

  • 我们发现，当我们用DFS进行处理的时候，对于某一条路径的某一个节点，我们可以维护两个信息，当前存储的数字序列，当前数字和离目标和少了多少。对于那个存储数字的那个序列，我们可以开一个全局数组，这样我们就没必要把这个当作参数进行传递了。

  • 然后我们讲讲如何DFS。

    • 边界：当我们到达左右节点为空的时候，说明我们到达了叶子节点，判断是否满足题目要求，不需要继续向下递归。
    • 递归条件，如果没有到达叶子节点，那么就可以继续想下进行递归操作，同时不断更新递归条件。
    • 每层递归最后记得回溯。

  • 代码,时间复杂度O(n),空间复杂度也是O(n)

    /*
struct TreeNode {
  int val;
  struct TreeNode *left;
  struct TreeNode *right;
  TreeNode(int x) :
          val(x), left(NULL), right(NULL) {
  }
};*/
class Solution {
public:
  vector<int> path;
  vector<vector<int> > ans;
  vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
      if(!root){
          return ans;
      }
      // 将这个节点的权值放入中间数组里面
      path.push_back(root->val);  
      // 出口
      if(!root->left&&!root->right&&root->val==expectNumber){ 
          ans.push_back(path);
      }else{
          // 继续递归
          if(root->left){  
              FindPath(root->left, expectNumber - root->val);
          }
          // 继续递归
          if(root->right){  
              FindPath(root->right, expectNumber - root->val);
          }
      }
      // 记得回溯
      path.pop_back(); 
      return ans;
  }
};

非递归写法，用栈模拟

  • 这个题目需要我们用栈模拟DFS，其实思路很简单，就是我们要保存每个位置的信息，这些信息包括当前结点，当前位置的和以及当前路径的情况。但是我们需要自己构造一个新的结构体来保存这些信息.但是这种写法空间复杂度较高，请谨慎使用。 
struct Node{
    // 当前结点
    TreeNode* r;
    // 当前路径
    vector<int> path;
    // 当前和
    int sum;
};
  • 代码如下，时间复杂度为O(n) 
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    // 我们自己构造出一个结构体，里面分别存储当前结点，当前路径和当前和
    struct Node{
        TreeNode* r;
        vector<int> path;
        int sum;
    };
    vector<vector<int> > ans;
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        // 判断为空的情况
        if(!root){
            return ans;
        }
        // 将这个节点的权值放入中间数组里面
        stack<Node> st;
        vector<int> path;
        // 先将根结点入队
        path.push_back(root->val);
        st.push(Node{root,path,root->val});
        while(!st.empty()){
            // 栈顶出队
            Node now = st.top();
            st.pop();
            // 判断是否满足题目的条件
            if(!now.r->left&&!now.r->right&&now.sum==expectNumber){
                ans.push_back(now.path);
            }else{
                // 左节点可以继续遍历
                if(now.r->left){
                    vector<int> tmp=now.path;
                    tmp.push_back(now.r->left->val);
                    st.push(Node{now.r->left,tmp,now.sum+now.r->left->val});
                }
                // 右边结点可以继续遍历
                if(now.r->right){
                    vector<int> tmp=now.path;
                    tmp.push_back(now.r->right->val);
                    st.push(Node{now.r->right,tmp,now.sum+now.r->right->val});
                }
            }
        }
        // 对最后的结果排序，按照字典序
        sort(ans.begin(),ans.end());
        return ans;
    }
};