算法:求二叉树的高度

问题引入(树之高度)

输入描述 对于一个二叉树，输入的第一行表示节点的个数n（1 ≤ n ≤ 1000，节点的编号为0到n-1）组成，下面是n-1行，每行有两个整数，第一个数表示父节点的编号，第二个数表示子节点的编号 输出描述 输出树的高度，为一个整数 测试用例 输入 5 0 1 0 2 1 3 1 4 输出 3

解决方法

使用递归法求树的高度

int getdeep_1(treeType root)
	{
		if(root!=null)
		{
			//返回树的叶子所在的最深处的高度
			return 1+Math.max(getdeep_1(root.left), getdeep_1(root.right));
		}
		return 0;
	}

使用层序遍历求树的高度

int getdeep_2(treeType root)
	{
		if(root!=null)
		{
			//借用队列先进先出的特性，按层遍历
			Queue<treeType> Q=new LinkedList<treeType>();
			Q.add(root);
			int deepth=0;//树的深度
			int length=0;//计数器
			int count=1;用以判断某一层结点是否都出队
			while(!Q.isEmpty())
			{
				treeType head=Q.poll();
				count--;//每次弹出，意味着这一层的某个结点已不在队列里了，要减1
				if(head.left!=null)
				{
					Q.add(head.left);
					length++;
				}
				if(head.right!=null)
				{
					Q.add(head.right);
					length++;
				}
				if(count==0)
				{
					//count=0标志着一层的结点已经访问完，要更新为下一层的结点数，length重置为0,树的深度加1
					count=Q.size();
					length=0;
					deepth++;
				}
			}
			return deepth;
		}
		return 0;
	}
}

代码

package james;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class TreeHigh
{
	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		treeType[] array=new treeType[in.nextInt()];
		for(int i=0;i<array.length;i++)
		{
			array[i]=new treeType(i);
		}
		int LEN=array.length;
		while(LEN-->1)
		{
			int n=in.nextInt();
			int m=in.nextInt();
			array[n].createTree(array[m]);
		}
		System.out.println("method_1:"+array[0].getdeep_1(array[0]));
		System.out.println("method_2:"+array[0].getdeep_2(array[0]));
	}
}

class treeType
{
	treeType left;
	treeType right;
	int value;
	public treeType(int nextInt) {
		this.value=nextInt;
	}

	public treeType() {
		// TODO Auto-generated constructor stub
	}

	//创建二叉树
	void createTree(treeType root)
	{
		if(root!=null)
		{
			if(this.left==null)
			{
				this.left=root;
				return;
			}
			if(this.right==null)
			{
				this.right=root;
				return;
			}
			else if(this.left!=null && this.right!=null)
			{
				System.out.println("子结点已满，无法创建");
				return;
			}
		}
	}
	
	//递归实现求树的高度
	int getdeep_1(treeType root)
	{
		if(root!=null)
		{
			return 1+Math.max(getdeep_1(root.left), getdeep_1(root.right));
		}
		return 0;
	}
	
	//使用层次遍历求树的高度
	int getdeep_2(treeType root)
	{
		if(root!=null)
		{
			//借用队列先进先出的特性
			Queue<treeType> Q=new LinkedList<treeType>();
			Q.add(root);
			int deepth=0;
			int length=0;
			int count=1;
			while(!Q.isEmpty())
			{
				treeType head=Q.poll();
				count--;
				if(head.left!=null)
				{
					Q.add(head.left);
					length++;
					
				}
				if(head.right!=null)
				{
					Q.add(head.right);
					length++;
				}
				if(count==0)
				{
					count=Q.size();
					length=0;
					deepth++;
				}
			}
			return deepth;
		}
		return 0;
	}
}

谁不想成功 梦醒成英雄 在你眼中我不同 (从无到有）