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.

分析

无

代码

  1. // Balanced Binary Tree
  2. // 时间复杂度O(n)，空间复杂度O(logn)
  3. public class Solution {
  4.     public boolean isBalanced (TreeNode root) {
  5.         return balancedHeight (root) >= 0;
  6.     }
  8.     /**
  9.      * Returns the height of `root` if `root` is a balanced tree,
  10.      * otherwise, returns `-1`.
  11.      */
  12.     private static int balancedHeight (TreeNode root) {
  13.         if (root == null) return 0;  // 终止条件
  15.         int left = balancedHeight (root.left);
  16.         int right = balancedHeight (root.right);
  18.         if (left < 0 || right < 0 || Math.abs(left - right) > 1) return -1;  // 剪枝
  20.         return Math.max(left, right) + 1; // 三方合并
  21.     }
  22. }

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/binary-tree/traversal/balanced-binary-tree.html