码农乌托邦

楠哥小站

楠哥,理想主义码农,就职于Google,现居纽约。


Balanced Binary Tree

判定平衡二叉树的题目是一道基本的数据结构题目,在Leetcode的OJ上也有相关的测试用例。二叉树的结构请参见《Leetcode中使用的二叉树结构》。

可以使用一个递归函数,递归的判断每个节点的左子树和右子树的高度是否相差1,但是这样的算法会产生很多次重复的计算,效率并不高。另外一种方法是设计一个递归函数,返回以每个节点为根的二叉树的高度,当左右子树返回的高度相差超过1时,则返回-1表示该树不平衡。这样的算法时间复杂度为O(n)。该算法的Java实现如下。

public class Solution {

	/**
	 * Given a binary tree, determine if it is height-balanced.
	 *For this problem, a height-balanced binary tree is defined as a binary 
	 *tree in which the depth of the two subtrees of every node never differ 
	 *by more than 1.
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		TreeNode root = new TreeNode(1);
		root.left = new TreeNode(2);
		root.right = new TreeNode(3);
		root.left.left = new TreeNode(4);
		root.left.right = new TreeNode(5);
		root.right.left = new TreeNode(6);
		root.right.right = new TreeNode(7);

		
		System.out.print(new Solution().isBalanced(root));
	}
	
	public boolean isBalanced(TreeNode root) {
        // Start typing your Java solution below
        // DO NOT write main() function
		
		if(height(root) == -1)
			return false;
		else
			return true;
    }
	
	public int height(TreeNode n){
		int left_b, right_b;
		
		if(n == null){
			return 0;
		}
		else{
			left_b = height(n.left);
			right_b = height(n.right);

			if (left_b == -1 || right_b == -1) {
				return -1;
			} else if (Math.abs(left_b - right_b) <= 1) {
				return Math.max(left_b, right_b)+1;
			} else {
				return -1;
			}
		}
	}

}
最近的文章

Climbing Stairs

爬楼梯问题是一道典型的递归问题和动态规划问题的入门级题目。题目描述是:给定一个n个台阶楼梯,每次可以上一个或者两个台阶,请问最终可以有多少种方法爬到顶层。使用递归的思路解决是,到达第K个楼梯的方法数目…

Technical, Career继续阅读
更早的文章

Leetcode中使用的二叉树结构

在leetcode中使用的二叉树,大多是"双指针"二叉树,即每个节点有指向其两个孩子的两个指针。同时,每个节点都有一个域存储该节点的int型值。每个节点写成一个类,该类每个域都是默…

Technical, Career继续阅读
comments powered by Disqus