当前位置:首页 > 开发 > 编程语言 > 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

    震惊

    震惊

编辑推荐
/* 在二元树中找出和为某一值的所有路径(树) 题目:输入一个整数和一棵二元树。 从树的根结点开始往
题目 题目:输入一个整数和一棵二元树。 从树的根结点开始往下访问一直到叶结点所经过的所有结点形
题目:输入一个整数和一棵二元树。 从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条
一 问题描述: 输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点
题目描述: 输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为
题目:输入一棵二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开
题目:输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树
问题定义: You are given a binary tree in which each node contains a value. Design an algorit
原文: You are given a binary tree in which each node contains a value. Design an algorithm t
一、题目:二叉树中和为某一值的路径 题目:输入一棵二叉树和一个整数,打印出二叉树中结点值的和为
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号