北京网站建设首选小峰,wordpress搜索屏蔽,网络管理软件免费,购物系统数据库设计题目描述
输入一颗二叉树的跟节点和一个整数#xff0c;打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
解题思路
要求一路径的和#xff0c;那么必然终止条件为叶子结点#xff0c;从根结点出发…题目描述
输入一颗二叉树的跟节点和一个整数打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
解题思路
要求一路径的和那么必然终止条件为叶子结点从根结点出发从左往右每条路径的和都与给定的值比较自然能求出。 但往往二叉树的题都会用到递归本身是二叉树那么子树必定为二叉树如果找到规律 我们可以这样想递归一次旧调用系统栈一次保存数据。既然要路径上的所有结点的和等于给定的值就说明给定的值减去路径的和等于0。我们就不难想到每次递归减去当前根结点的值一直到叶子结点如果最后的值等于叶子结点的值那不就正好可以求解此题。 我们要考虑特殊情况如果二叉树只有一个结点并恰巧那个结点的值等于给定的值呢所以每回减去当前根结点的值前先判断是否相等再减去。 如果到叶子结点不相等那么就往上走再往右边走。 有了上述思路就不难写出如下代码
代码实现
class Solution {vectorvectorint result;vectorint path;
public:void find(TreeNode* root,int expectnum){if(root NULL)return ;path.push_back(root-val);if(!root-left!root-right expectnum root-val)result.push_back(path);else{if(root-left)find(root-left,expectnum-root-val);if(root-right)find(root-right,expectnum-root-val);}path.pop_back();}vectorvectorint FindPath(TreeNode* root,int expectNumber) {find(root,expectNumber);return result;}
};
