Ex34 二叉树中和为某一值的路径

题目描述

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

解题思路

递归地遍历左右子树，直至遇到叶子结点，即!root->left && !root->right的结点，并且remain == 0的时候，将临时存储的vec，放入最终结果vecs。

代码

class Solution
{
public:
  std::vector<std::vector<int> >
  pathSum (TreeNode *root, int sum)
  {
    std::vector<std::vector<int> > vecs;
    if (!root)
      return vecs;
    std::vector<int> vec;
    vec.push_back (root->val);
    int remain = sum - root->val;
    if (!root->left && !root->right && remain == 0)
      {
        vecs.push_back (vec);
        return vecs;
      }
    path_sum_core (root->left, vec, vecs, remain);
    vec.clear ();
    vec.push_back (root->val);
    path_sum_core (root->right, vec, vecs, remain);
    return vecs;
  }

private:
  void
  path_sum_core (TreeNode *root, std::vector<int> vec,
                 std::vector<std::vector<int> > &vecs, int remain)
  {
    if (!root)
      {
        return;
      }
    vec.push_back (root->val);
    remain -= root->val;
    if (!root->left && !root->right && remain == 0)
      {
        vecs.push_back (vec);
        return;
      }
    path_sum_core (root->left, vec, vecs, remain);
    path_sum_core (root->right, vec, vecs, remain);
    remain += root->val;
    vec.pop_back ();
  }
};

结果

执行结果：通过

执行用时：28 ms, 在所有 C++ 提交中击败了19.59%的用户

内存消耗：39.2 MB, 在所有 C++ 提交中击败了5.56%的用户