首页 > 其他 > 详细

Balanced Binary Tree

时间:2017-05-31 09:24:00      阅读:285      评论:0      收藏:0      [点我收藏+]

Note:
a balaced tree needs to be balaced all the time. So it is important remember the status of each subtree. If it is not balaced in the middle, the full tree is not balaced. For example, this tree is not balaced: {1,2,3,4,#,5,6,7,8,9,10,11,12}

/**
 * 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 {
        public int depth;
        public boolean isBalanced;
        public ResultType(int depth, boolean isBalanced) {
            this.depth = depth;
            this.isBalanced = isBalanced;
        } 
    } 
    public boolean isBalanced(TreeNode root) {
        // write your code here
        if (root == null) {
            return true;
        }
        
        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 (Math.abs(left.depth - right.depth) <= 1 && left.isBalanced && right.isBalanced) {
            return new ResultType(Math.max(left.depth, right.depth) + 1, true);
        } else {
            //System.out.println(root.val);
            return new ResultType(Math.max(left.depth, right.depth) + 1, false);
        }
        
    }
}

 

Balanced Binary Tree

原文:http://www.cnblogs.com/codingEskimo/p/6922554.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!