C++ 二叉树路径之和

给定一个二叉树与整数sum，找出所有从根节点到叶节点的路径，这些路径上的节点值累加和为sum。

#include<stdio.h>
#include<vector>
struct TreeNode
{
 int val;
 TreeNode* left;
 TreeNode* right;
 TreeNode(int x) : val(x), left(NULL), right(NULL){}
};
class Solution
{
public:
 Solution() {};
 ~Solution() {};
 void preorder (TreeNode* node, int sum, int& path_val, std::vector<int>& path, std::vector<std::vector<int>>& result)
 {
  if (!node)
  {
   return;
  }
  path_val += node->val;
  path.push_back(node->val);
  if (!node->left && !node->right && path_val == sum)
  {
   result.push_back(path);
  }
  preorder(node->left, sum, path_val, path, result);
  preorder(node->right, sum, path_val, path, result);
  path_val -= node->val;
  path.pop_back();
 }
};
int main()
{
 TreeNode a(5);
 TreeNode b(4);
 TreeNode c(8);
 TreeNode d(11);
 TreeNode e(13);
 TreeNode f(4);
 TreeNode g(7);
 TreeNode h(2);
 TreeNode x(5);
 TreeNode y(1);
 a.left = &b;
 a.right = &c;
 b.left = &d;
 c.left = &e;
 c.right = &f;
 d.left = &g;
 d.right = &h;
 f.left = &x;
 f.right = &y;
 Solution solve;
 std::vector<std::vector<int>> result;
 std::vector<int> path;
 int path_val = 0;
 solve.preorder(&a, 22, path_val ,path,result);
 for (int i = 0; i < result.size(); i++)
 {
  for (int j = 0; j < result[i].size(); j++)
  {
   printf("[%d]",result[i][j]);
  }
  printf("n");
 }
 return 0;
}

运行结果为：

[5][4][11][2]
[5][8][4][5]

最后

以上就是落寞大叔为你收集整理的C++ 二叉树路径之和的全部内容，希望文章能够帮你解决C++ 二叉树路径之和所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。