首页 / 算法 / 二叉树的和为某一条路径
二叉树的和为某一条路径
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了二叉树的和为某一条路径，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2953字，纯文字阅读大概需要5分钟。
内容图文
题目描述
输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
//非递归版本
//思路：
1.按先序遍历把当前节点cur的左孩子依次入栈同时保存当前节点，每次更新当前路径的和sum；
2.判断当前节点是否是叶子节点以及sum是否等于expectNumber，如果是，把当前路径放入结果中。
3.遇到叶子节点cur更新为NULL，此时看栈顶元素，如果栈顶元素的把栈顶元素保存在last变量中，同时弹出栈顶元素，当期路径中栈顶元素弹出，sum减掉栈顶元素，这一步骤不更改cur的值；
4.如果步骤3中的栈顶元素的右孩子存在且右孩子之前没有遍历过，当前节点cur更新为栈顶的右孩子，此时改变cur=NULL的情况。
#include <iostream>
#include <vector>
using namespace std;
struct TreeNode{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL){}
}
vector<vector<int> > FindPath(TreeNode *root, int expectNumber){
vector<vector<int> > res;
if (root == NULL)
return res;
stack<TreeNode *> s;
s.push(root);
int sum = 0; //当前和
vector<int> curPath; //当前路径
TreeNode *cur = root; //当前节点
TreeNode *last = NULL; //保存上一个节点
while (!s.empty()){
if (cur == NULL){
TreeNode *temp = s.top();
if (temp->right != NULL && temp->right != last){
cur = temp->right; //转向未遍历过的右子树
}else{
last = temp; //保存上一个已遍历的节点
s.pop();
curPath.pop_back(); //从当前路径删除
sum -= temp->val;
} }
else{
s.push(cur);
sum += cur->val;
curPath.push_back(cur->val);
if (cur->left == NULL && cur->right == NULL && sum == expectNum){
res.push_back(curPath);
}
cur = cur->left; //先序遍历，左子树先于右子树
}
}
return res;
}
递归
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
vector<vector<int> >allres;
vector<int> tmp;
void dfs(TreeNode *node, int left) {
tmp.push_back(node->val);
if(left-node->val == 0 && !node->left && !node->right)
allres.push_back(tmp);
else {
if(node->left) dfs(node->left,left-node->val);
if(node->right) dfs(node->right,left-node->val);
}
tmp.pop_back();
}
public:
vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
if(root) dfs(root,expectNumber);
return allres;
}
};
/* 思路更为清晰的递归方式 -- path与ret均定义在函数内部 */
/* 递归方式 */
class Solution {
void DFSFindPath(TreeNode* root, int rest, vector<vector<int>> &path, vector<int> &ret)
{
rest -= root->val; // 减去当前结点的值
ret.push_back(root->val);
// 如果是叶子结点，则看此时路径和是否等于exceptNumber，是则保留该路径
if(root->left == nullptr && root->right == nullptr)
if(rest == 0) path.push_back(ret);
// 如果不是叶子结点，若rest != 0,则递归进入左右子树（注：若rest==0，则删除该结点后返回）
if( rest != 0 && root->left != nullptr)
DFSFindPath(root->left,rest,path,ret);
if( rest != 0 && root->right != nullptr)
DFSFindPath(root->right,rest,path,ret);
ret.pop_back(); // 退出该结点前，在路径中删除该结点
}
public:
vector<vector<int> > FindPath(TreeNode* root,int expectNumber)
{
vector<vector<int>> path;
vector<int> ret;
if(root != nullptr)
DFSFindPath(root,expectNumber,path,ret);
return path;
}
};
原文：http://www.cnblogs.com/dd2hm/p/7308769.html
内容总结
以上是互联网集市为您收集整理的二叉树的和为某一条路径全部内容，希望文章能够帮你解决二叉树的和为某一条路径所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】