LintCode 93. Balanced Binary Tree 原创Java参考解答

LintCode 93. Balanced Binary Tree 原创Java参考解答

问题描述

http://www.lintcode.com/en/problem/balanced-binary-tree/

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.

Example

Given binary tree A = {3,9,20,#,#,15,7}, B = {3,#,20,15,7}

A)  3            B)    3 
   / \                  \
  9  20                 20
    /  \                / \
   15   7              15  7

The binary tree A is a height-balanced binary tree, but B is not.

解题思路

题目要求去判断一颗二叉树是否高度平衡,即任何左右两树高度差不得大于1。

实现可以参考下面代码,先构造一个ResultType的类别,包括最大高度和是否平衡的属性。

接着建一个helper方法,分支返回对树支点进行判断后的ResultType。

参考代码

/** 
 * Definition of TreeNode: 
 * public class TreeNode { 
 *     public int val; 
 *     public TreeNode left, right; 
 *     public TreeNode(int val) { 
 *         this.val = val; 
 *         this.left = this.right = null; 
 *     } 
 * } 
 */ 
public class Solution { 
    /** 
     * @param root: The root of binary tree. 
     * @return: True if this Binary tree is Balanced, or false. 
     */ 
    private class ResultType { 
        private int maxHeight; 
        private boolean isBalanced; 
         
        public ResultType(int maxHeight, boolean isBalanced) { 
            this.maxHeight = maxHeight; 
            this.isBalanced = isBalanced; 
        } 
    }  
     
    public boolean isBalanced(TreeNode root) { 
        return helper(root).isBalanced; 
    } 
     
    private ResultType helper(TreeNode root) { 
        if (root == null) { 
            return new ResultType(0, true); 
        } 
         
        ResultType left = helper(root.left); 
        ResultType right = helper(root.right); 
         
        if (!left.isBalanced || !right.isBalanced) { 
            return new ResultType(Integer.MIN_VALUE, false); 
        } 
 
        if (Math.abs(left.maxHeight - right.maxHeight) > 1) { 
            return new ResultType(Integer.MIN_VALUE, false); 
        } 
         
        return new ResultType(Math.max(left.maxHeight, right.maxHeight) + 1, true); 
    } 
} 

相关题目

LintCode All in One 原创题目讲解汇总

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注