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. class Solution {
  4. public:
  5.     bool isBalanced (TreeNode* root) {
  6.         return balancedHeight (root) >= 0;
  7.     }
  9.     /**
  10.      * Returns the height of `root` if `root` is a balanced tree,
  11.      * otherwise, returns `-1`.
  12.      */
  13.     int balancedHeight (TreeNode* root) {
  14.         if (root == nullptr) return 0;  // 终止条件
  16.         int left = balancedHeight (root->left);
  17.         int right = balancedHeight (root->right);
  19.         if (left < 0 || right < 0 || abs(left - right) > 1) return -1;  // 剪枝
  21.         return max(left, right) + 1; // 三方合并
  22.     }
  23. };

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