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

java-11.二叉树中节点的最大距离

发表于: 2012-01-11   作者:bylijinnan   来源:转载   浏览:
摘要: import java.util.ArrayList; import java.util.List; public class MaxLenInBinTree { /* a. 1 / \ 2 3 / \ / \ 4 5 6 7 max=4 pass "root"
import java.util.ArrayList;
import java.util.List;


public class MaxLenInBinTree {

	/*
	 a.			1
	 		   /  \
	 		  2    3
	 		 / \  / \
	 		4   5 6  7
	 	max=4	pass "root"
	 b.			1
	 		   /  \
	 		  2    3
	 		 / \    
	 		4   5    
	 	   /     \
	 	  6       7
	 	 /         \
	 	8           9
	 	max=6. do not pass "root"
	 */
	public static void main(String[] args) {
		int[] a={1,2,3,4,5,6,7};
		//store in LevelOrder,Complete Binary Tree. 0==no child
		int[] b={1,2,3,4,5,0,0,6,0,0,7,0,0,0,0,8,0,0,0,0,0,0,9};
		MaxLenInBinTree m=new MaxLenInBinTree();
		Node aRoot=m.createTree(b);
		m.findMaxLen(aRoot);
		System.out.println(m.maxLen);
		
	}

	private int maxLen=0;
	
	public void findMaxLen(Node node){
		
		if(node==null) return ;
		
		if(node.getLeft()==null){
			node.setMaxLeftLen(0);
		}
		if(node.getRight()==null){
			node.setMaxRightLen(0);
		}
		
		if(node.getLeft()!=null){
			findMaxLen(node.getLeft());
		}
		if(node.getRight()!=null){
			findMaxLen(node.getRight());
		}
		
		if(node.getLeft()!=null){
			int temp=0;
			Node left=node.getLeft();
			if(left.getMaxLeftLen()>left.getMaxRightLen()){
				temp=left.getMaxLeftLen();
			}else{
				temp=left.getMaxRightLen();
			}
			node.setMaxLeftLen(temp+1);
		}
		if(node.getRight()!=null){
			int temp=0;
			Node right=node.getRight();
			if(right.getMaxLeftLen()>right.getMaxRightLen()){
				temp=right.getMaxLeftLen();
			}else{
				temp=right.getMaxRightLen();
			}
			node.setMaxRightLen(temp+1);
		}
		if(maxLen<node.getMaxLeftLen()+node.getMaxRightLen()){
			maxLen=node.getMaxLeftLen()+node.getMaxRightLen();
		}
	}
	
	public Node createTree(int[] data){
		List<Node> nodeList=new ArrayList<Node>();
		for(int each:data){
			Node n=new Node(each);
			nodeList.add(n);
		}
		int lastRootIndex=data.length/2-1;
		for(int i=0;i<=lastRootIndex;i++){
			Node root=nodeList.get(i);
			Node left=nodeList.get(i*2+1);
			if(left.getData()!=0){
				root.setLeft(left);
			}else{
				root.setLeft(null);
			}
			if(i*2+2<data.length){
				Node right=nodeList.get(i*2+2);
				if(right.getData()!=0){
					root.setRight(right);
				}else{
					root.setRight(null);
				}
			}
			
		}
		Node root=nodeList.get(0);
		return root;
	}
	class Node{
		private int data;
		private Node left;
		private Node right;
		private int maxLeftLen;//the max length of leftTree
		private int maxRightLen;
		
		public Node(int i){
			data=i;
		}
		public int getData() {
			return data;
		}
		public void setData(int data) {
			this.data = data;
			this.left=null;
			this.right=null;
		}
		public Node getLeft() {
			return left;
		}
		public void setLeft(Node left) {
			this.left = left;
		}
		public Node getRight() {
			return right;
		}
		public void setRight(Node right) {
			this.right = right;
		}
		public int getMaxLeftLen() {
			return maxLeftLen;
		}
		public void setMaxLeftLen(int maxLeftLen) {
			this.maxLeftLen = maxLeftLen;
		}
		public int getMaxRightLen() {
			return maxRightLen;
		}
		public void setMaxRightLen(int maxRightLen) {
			this.maxRightLen = maxRightLen;
		}
	}
}

java-11.二叉树中节点的最大距离

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
《编程之美: 求二叉树中节点的最大距离》的另一个解法 原文地址:http://www.cnblogs.com/miloyip/a
问题定义 如果我们把二叉树看成一个图,父子节点之间的连线看成是双向的,我们姑且定义"距离"为两节
方法一:求二叉树中节点的最大距离,等同于“计算每个节点的左子树和右子树的高度和,取最大值” 方
问题定义 如果我们把二叉树看成一个图,父子节点之间的连线看成是双向的,我们姑且定义"距离"为两节
今天中午的时候有人问了我一个问题:求二叉树中节点的最大距离。这是《编程之美》上的一个问题。 花
求二叉树中节点的最大距离 题目: 如果我们把二叉树看成一个图,父子节点之间的连线看成是双向的,
问题定义 参考资料 [1] http://www.cs.duke.edu/courses/spring00/cps100/assign/trees/diameter.ht
递归求解,最大距离总是在一下两种情况产生 情况1: 最大路径经过root 这个例子中,最长路径经过root
《编程之美: 求二叉树中节点的最大距离》的另一个解法 问题定义 如果我们把二叉树看成一个图,父子
问题来源:《编程之美》3.8 求二叉树节点的最大距离 如果把二叉树看成一个图,父子节点之间的连线看
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号