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

java-判断二叉树是不是平衡

发表于: 2012-02-11   作者:bylijinnan   来源:转载   浏览:
摘要: 参考了 http://zhedahht.blog.163.com/blog/static/25411174201142733927831/ 但是用java来实现有一个问题。 由于Java无法像C那样“传递参数的地址,函数返回时能得到参数的值”,唯有新建一个辅助类:AuxClass import ljn.help.*; public class BalancedBTree {
参考了 http://zhedahht.blog.163.com/blog/static/25411174201142733927831/
但是用java来实现有一个问题。
由于Java无法像C那样“传递参数的地址,函数返回时能得到参数的值”,唯有新建一个辅助类:AuxClass

import ljn.help.*;
public class BalancedBTree {

	/**
	 * Q判断二叉树是不是平衡
 		1
	   / \
	  2   3
     / \   \
    4   5   6
       /
      7
	 */
	public static void main(String[] args) {

		int[][] threeBTrees={
				{1,2,3,4,5,0,6,0,0,7},//balanced
				{1,2,3,4,5,0,0,0,0,7},//not balanced
				};
		for(int[] each:threeBTrees){
			Node node=Helper.createTree(each);
			AuxClass aux= new AuxClass();
			boolean result=isBalanced(node,aux);
			System.out.println(result);
		}
	}

	/*
	 * 如果我们用后序遍历的方式遍历二叉树的每一个结点,在遍历到一个结点之前我们已经遍历了它的左右子树。
	 * 只要在遍历每个结点的时候记录它的深度(某一结点的深度等于它到叶节点的路径的长度),
	 * 我们就可以一边遍历一边判断每个结点是不是平衡的
	 * C/C++代码可参见 http://zhedahht.blog.163.com/blog/static/25411174201142733927831/
	 * 由于Java无法像C那样“传递参数的地址,函数返回时能得到参数的值”,唯有新建一个辅助类:AuxClass
	 */
	public static boolean isBalanced(Node node,AuxClass aux){
		if(node==null){
			aux.depth=0;
			return true;
		}
		AuxClass left=new AuxClass();
		AuxClass right=new AuxClass();
		//get leftTreeDepth and rightTreeDepth of a node.If the 'diff' is bigger than 1,return false;true otherwise
		if(isBalanced(node.getLeft(),left)&&isBalanced(node.getRight(),right)){
			int leftDepth=left.depth;
			int rightDepth=right.depth;
			int diff=leftDepth-rightDepth;
			if(diff==1||diff==-1||diff==0){
				aux.depth=leftDepth>rightDepth?leftDepth+1:rightDepth+1;
				return true;
			}
		}
		return false;
	}
	public static class AuxClass{
		private int depth;
	}
}


java-判断二叉树是不是平衡

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
题目:输入一棵二叉树的根结点,判断该树是不是平衡二叉树。如果某二叉树中任意结点的左右子树的深
输入一棵二叉树的根结点,判断该树是不是平衡二叉树。如果某二叉树中任意结点的左右子树的深度相差
题目来自http://zhedahht.blog.163.com/blog/#m=0 题目:输入一棵二叉树的根结点,判断该树是不是平
问题描述:输入一棵二叉树的根结点,判断该树是不是平衡二叉树。如果某二叉树中任意结点的左右子树
题目:输入一棵二叉树的根结点,判断该树是不是平衡二叉树。如果某二叉树中任意结点的左右子树的深
程序员面试题精选100题(60)-判断二叉树是不是平衡 题目:输入一棵二叉树的根结点,判断该树是不是平
平衡二叉树AVL也是一个二叉搜索树,所以二叉搜索树的一些方法对他也适用。他跟二叉搜索树的区别在于
#返回上一级 @Author: 张海拔 @Update: 2014-2-2 @Link: http://www.cnblogs.com/zhanghaiba/p/3537
import java.util.*; public class BinaryTree { protected Node root; public BinaryTree(Node roo
我的代码:直接用了以前那个求二叉树某一个条路径的和为特定值的思想 源代码 struct TreeNode{ int
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号