当前位置:首页 > 开发 > 编程语言 > Java > 正文

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

发表于: 2012-01-08   作者:bylijinnan   来源:转载   浏览:
摘要: /* * 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
/*
	 * 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();
	}

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

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号