《剑指offer》面试题25 二叉树中和为某一值的路径 Java版
2024-10-07 05:36:47
（判断是否有从根到叶子节点的路径，其和为给定值。记录这些路径。）
我的方法：这道题我是按照回溯的思路去做的，我们需要一个数据结构来保存和删除当前递归函数中添加的值。这里要打印一条路径，我们可以选择List、栈等，它们都可以很方便的删除掉末尾的元素从而保护现场，也可以选择String，只需要在进入递归的时候创建一个和参数一样的值，也能做到在子函数退出的时候保护现场的效果。递归的时候先判断是否满足条件，然后添加本节点的值往下递归。
public void findPath(TreeNode root, int target){
if (root == null) {
return;
}
Stack<TreeNode> path = new Stack<TreeNode>();
int sum = 0;
find2(path, root, sum, target);
}
private void find(Stack<TreeNode> path, TreeNode root, int sum, int target){
if(sum > target)return;
if(root == null && sum < target)return;
if(root == null && sum == target){
for(TreeNode treeNode : path){
System.out.print(treeNode.val+" ");
}
System.out.println();
return;
}
if(root != null){
if(root.left != null || root.right != null){//如果左右子树有不空的，向下寻找
if(root.left != null){
path.push(root);
sum += root.val;
find(path, root.left, sum, target);
sum -= root.val;
path.pop();
}
if(root.right != null){
path.push(root);
sum += root.val;
find(path, root.right, sum, target);
sum -= root.val;
path.pop();
}
}else{//如果左右子树都空了，说明到了叶子节点
path.push(root);
sum += root.val;
//发送结束信息
find(path, null, sum, target);
sum -= root.val;
path.pop();
}
}
}
书中方法：先添加本节点值，然后判断是否满足条件，接着往下递归。
public void findPath(TreeNode root, int target){
if (root == null) {
return;
}
Stack<TreeNode> path = new Stack<TreeNode>();
int sum = 0;
find2(path, root, sum, target);
}
private void find2(Stack<TreeNode> path, TreeNode root, int sum, int target){
path.push(root);
sum += root.val;
if(sum > target){
path.pop();
return;
}
if(sum == target && root.left == null && root.right == null){
//从栈底到栈顶打印
for(TreeNode treeNode : path){
System.out.print(treeNode.val+" ");
}
System.out.println();
}
if(root.left != null)find2(path, root.left, sum, target);
if(root.right != null)find2(path, root.right, sum, target);
//保护现场
path.pop();
}
这道题如果是任意路径，而不要求从根节点到叶子节点。那么思路应该是分为两层递归，外层递归就是遍历二叉树，内层寻找路径。
最新文章
- Ubuntu14.04或16.04下安装JDK1.8+Scala+Hadoop2.7.3+Spark2.0.2
- XCOJ 1103 (LCA+树链最大子段和)
- [转]Linq中GroupBy方法的使用总结
- Linux -Yum 命令详解
- hihocoder 第一周 最长回文字串
- java常用重构优化总结--自己亲身体验
- ISO15693标准详细介绍
- Dictionary到List转换中的性能问题 转
- Android实现左右滑动指引效果
- 【测试】这是用微软word发布的博客
- POJ 2524 ：Ubiquitous Religions
- Sliverlight之 故事板
- Application对象
- [LeetCode] Friend Circles 朋友圈
- python基础一 ------如何获取多个字典相同的键
- 设置outlook 2013 默认的ost路径
- CentOS 7.4 初次手记：第三章 CentOS基础了解
- Apache版本hadoop-2.6.0.tar.gz平台下搭建Hue
- TNS-12535: TNS:operation timed out、TNS-00505: Operation timed out
- kali linux之取证