首页 > 代码库 > [leetcode] Balanced Binary Tree

[leetcode] 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.

https://oj.leetcode.com/problems/balanced-binary-tree/

 

思路:注意不要写成先序遍历的顺序,会造成多次遍历树,应该采用后续遍历的顺序依次判断。

  注意java的没有引用传递,所以用了一个wrap类。

 

/* *  be careful about the order of traversal!!!don‘t do recursion in recursion that resulting traverse the tree many times. *      so we need to return the height and isBalanced of a node at the same time, but we can only return one, so if we use C++ *      we can use reference, but it‘s java... so we have to wrap a primitive or using an array. * https://oj.leetcode.com/discuss/3931/can-we-have-a-better-solution * http://www.cnblogs.com/remlostime/archive/2012/10/27/2742987.html *  */public class Solution {    public boolean isBalanced(TreeNode root) {        Height height = new Height();        return checkBalanced(root, height);    }    private boolean checkBalanced(TreeNode root, Height h) {        if (root == null) {            h.height = 0;            return true;        }        Height lh = new Height();        Height rh = new Height();        boolean leftBalanced = checkBalanced(root.left, lh);        boolean rightBalanced = checkBalanced(root.right, rh);        h.height = Math.max(lh.height, rh.height) + 1;        return leftBalanced && rightBalanced && (Math.abs(lh.height - rh.height) <= 1);    }    public static void main(String[] args) {        TreeNode root = new TreeNode(5);        root.right = new TreeNode(7);        root.right.left = new TreeNode(3);        root.right.left.right = new TreeNode(3);        root.left = new TreeNode(3);        System.out.println(new Solution().isBalanced(root));    }    private static class Height {        int height;    }}
View Code