`

java-4.-在二元树中找出和为某一值的所有路径 .

阅读更多
/*
	 * 0.use a TwoWayLinkedList to store the path.when the node can't be path,you should/can delete it.
	 * 1.curSum==exceptedSum:if the lastNode is TreeNode,printPath();delete the node otherwise
	 * 2.curSum>exceptedSum:return;
	 * 3.curSum<exceptedSum:push the node to path,continue in LeftTree and RightTree
	 */
	public void findSubTree(Node curNode,int exceptedSum){
		Node pathNode=null;
		int curSum=0;
		findSubTreeHelp(curNode,pathNode,curSum,exceptedSum);
	}
	public void findSubTreeHelp(Node curNode,Node pathNode,int curSum,int exceptedSum){
		curSum+=curNode.getVal();
		if(curSum>exceptedSum){
			return;
		}
		Node newNode=new Node(curNode.getVal());
		if(pathNode==null){
			pathNode=newNode;
		}else{
			pathNode.right=newNode;
			newNode.left=pathNode;
			pathNode=newNode;
		}
		if(curSum==exceptedSum){
			if(curNode.getLeft()==null&&curNode.getRight()==null){
				printPath(pathNode);
			}else{
				pathNode=deletePathNode(pathNode);
			}
		}
		if(curSum<exceptedSum){
			if(curNode.getLeft()!=null){
				findSubTreeHelp(curNode.getLeft(),pathNode,curSum,exceptedSum);
			}
			if(curNode.getRight()!=null){
				findSubTreeHelp(curNode.getRight(),pathNode,curSum,exceptedSum);
			}
		}
	}
	public Node deletePathNode(Node node){
		Node pathNode=node.getLeft();
		pathNode.right=null;
		return pathNode;
	}
	public void printPath(Node node){
		if(node==null)return;
		while(node.getLeft()!=null){
			node=node.getLeft();
		}
		while(node!=null){
			System.out.print(node.getVal()+",");
			node=node.getRight();
		}
		System.out.println();
	}
0
1
分享到:
评论

相关推荐

    java数据结构和算法

    ##### 1.2.5 在二元树中找出和为某一值的所有路径 - **问题描述**:给定一个二叉树和一个整数 sum,找出所有和为 sum 的路径。 - **解决方案**: - 使用深度优先搜索(DFS)遍历二叉树。 - 对于每个节点,递归地...

    Java写的一个数组的中,m个元素的组合问题

    数组的组合问题通常涉及到组合数学和算法设计,它可以帮助我们找出所有可能的子集或对,而无需考虑顺序。 标题“Java写的一个数组的中,m个元素的组合问题”提示我们要解决的是从给定数组中选取m个元素的所有可能...

    微软最新面试题目

    在二元树中找出和为某一值的所有路径** - **题目背景**:二叉树作为一种重要的数据结构,在算法设计中有着广泛的应用。本题要求在给定的二叉树中找到所有节点值之和等于给定值的路径。 - **数据结构定义**:题目...

    微软等公司数据结构+算法面试100题(含答案)

    在二元树中找出和为某一值的所有路径 #### 题目描述 给定一个整数target和一棵二叉树,找到所有从根节点到叶子节点且路径上的节点值之和等于target的路径。 #### 示例 假设target为22,给定二叉树如下: ``` 10 ...

    2021-2022计算机二级等级考试试题及答案No.9556.docx

    其中,回溯法是一种通过跟踪代码执行路径来找出错误来源的方法。 9. .NET框架提供了一个公共语言运行时环境(CLR),它负责内存管理、垃圾回收等任务。 10. 模块独立性的度量标准包括耦合性和内聚性。降低耦合性和...

    购物篮分析源代码.zip

    在这个场景中,“购物篮分析源代码.zip”文件包含了一组用于实现购物篮分析的Java源代码。这个压缩包里有四个主要的Java类(MBAMapper、Driver、Combination、MBAReduce)以及一个数据文件(data.txt)。接下来,...

    安徽大学2011级离散数学(下)实验

    4. **格理论**:第四题要求判断一个代数结构是否为格,并绘制哈斯图。格是一种特殊的偏序集,具有最大元和最小元,且任意两个元素都有上确界和下确界。 5. **最邻近法**:第五题涉及P274页的最邻近法,这通常指的是...

    中兴笔试试题(偏软件)

    从给定的文件信息中,我们可以总结出一系列与IT领域,特别是软件开发和编程相关的知识点。下面将逐一解析这些知识点: ### 数据库操作与恢复 #### 核心概念 数据库的核心是**数据管理**,它涉及到数据的组织、...

    Solve:桥梁、水壶和8个自行解决的拼图问题

    这涉及到二元一次方程组的解法,以及动态规划或递归策略来找出解决方案。 3. **8个自行解决的拼图问题**:这可能是指8-puzzle(8个方块的滑动拼图)或其他类似的逻辑拼图游戏。这些游戏通常具有一定的哈希函数和...

Global site tag (gtag.js) - Google Analytics