LeetCode 110: Balanced Binary Tree (Postorder Height Pruning)
LeetCode 110TreeDFSInterviewToday we solve LeetCode 110 - Balanced Binary Tree.
Source: https://leetcode.com/problems/balanced-binary-tree/
English
Problem Summary
Given the root of a binary tree, determine whether it is height-balanced. A tree is balanced if for every node, the height difference between its left and right subtrees is at most 1.
Key Insight
Instead of recalculating subtree heights repeatedly, compute height with postorder DFS and return a failure sentinel when imbalance is found. Once a subtree is unbalanced, bubble up immediately.
Brute Force and Limitations
Brute force checks each node by separately computing left and right heights, then recursing. Height calculation itself is O(n), so repeated work can degrade to O(n^2) on skewed trees.
Optimal Algorithm Steps
1) Define height(node) that returns subtree height, or -1 if unbalanced.
2) Base case: null returns 0.
3) Recursively get leftHeight and rightHeight; if either is -1, propagate -1.
4) If |leftHeight - rightHeight| > 1, return -1.
5) Otherwise return max(leftHeight, rightHeight) + 1.
6) Final answer is height(root) != -1.
Complexity Analysis
Time: O(n), each node visited once.
Space: O(h) recursion stack, worst-case O(n), average O(log n) for balanced trees.
Common Pitfalls
- Using top-down repeated height calls, causing quadratic complexity.
- Forgetting to early-stop when one subtree already returns unbalanced.
- Mixing “height” and “balanced state” into separate traversals unnecessarily.
- Misdefining empty tree height (should be 0).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isBalanced(TreeNode root) {
return height(root) != -1;
}
private int height(TreeNode node) {
if (node == null) return 0;
int lh = height(node.left);
if (lh == -1) return -1;
int rh = height(node.right);
if (rh == -1) return -1;
if (Math.abs(lh - rh) > 1) return -1;
return Math.max(lh, rh) + 1;
}
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isBalanced(root *TreeNode) bool {
return height(root) != -1
}
func height(node *TreeNode) int {
if node == nil {
return 0
}
lh := height(node.Left)
if lh == -1 {
return -1
}
rh := height(node.Right)
if rh == -1 {
return -1
}
if abs(lh-rh) > 1 {
return -1
}
if lh > rh {
return lh + 1
}
return rh + 1
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isBalanced(TreeNode* root) {
return height(root) != -1;
}
private:
int height(TreeNode* node) {
if (!node) return 0;
int lh = height(node->left);
if (lh == -1) return -1;
int rh = height(node->right);
if (rh == -1) return -1;
if (abs(lh - rh) > 1) return -1;
return max(lh, rh) + 1;
}
};# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isBalanced(self, root) -> bool:
return self.height(root) != -1
def height(self, node):
if not node:
return 0
lh = self.height(node.left)
if lh == -1:
return -1
rh = self.height(node.right)
if rh == -1:
return -1
if abs(lh - rh) > 1:
return -1
return max(lh, rh) + 1/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
var isBalanced = function(root) {
return height(root) !== -1;
};
function height(node) {
if (node === null) return 0;
const lh = height(node.left);
if (lh === -1) return -1;
const rh = height(node.right);
if (rh === -1) return -1;
if (Math.abs(lh - rh) > 1) return -1;
return Math.max(lh, rh) + 1;
}中文
题目概述
给定二叉树根节点，判断该树是否“高度平衡”。平衡定义为：对每个节点，左右子树高度差不超过 1。
核心思路
用后序 DFS一次性完成“求高度 + 判平衡”：若某子树已失衡，则返回哨兵值 -1 并向上层快速传播，避免无意义继续计算。
暴力解法与不足
暴力做法是对每个节点都单独递归计算左右子树高度，再递归检查子节点。这样会重复计算大量高度，退化情况下时间复杂度可达 O(n^2)。
最优算法步骤
1）定义函数 height(node)：返回子树高度；若失衡返回 -1。
2）空节点返回 0。
3）递归拿到左高 lh 与右高 rh，若任一为 -1，直接返回 -1。
4）若 |lh-rh| > 1，当前节点失衡，返回 -1。
5）否则返回 max(lh, rh)+1。
6）最终判断 height(root) != -1 即可。
复杂度分析
时间复杂度：O(n)，每个节点最多访问一次。
空间复杂度：O(h) 递归栈，最坏 O(n)，平衡树平均 O(log n)。
常见陷阱
- 仍使用“每个节点重复求高度”的写法，导致超时风险。
- 子树已失衡却未及时剪枝返回。
- 把“高度计算”和“平衡判断”拆成多次遍历，逻辑更复杂且更慢。
- 空树高度定义错误（应为 0）。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isBalanced(TreeNode root) {
return height(root) != -1;
}
private int height(TreeNode node) {
if (node == null) return 0;
int lh = height(node.left);
if (lh == -1) return -1;
int rh = height(node.right);
if (rh == -1) return -1;
if (Math.abs(lh - rh) > 1) return -1;
return Math.max(lh, rh) + 1;
}
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isBalanced(root *TreeNode) bool {
return height(root) != -1
}
func height(node *TreeNode) int {
if node == nil {
return 0
}
lh := height(node.Left)
if lh == -1 {
return -1
}
rh := height(node.Right)
if rh == -1 {
return -1
}
if abs(lh-rh) > 1 {
return -1
}
if lh > rh {
return lh + 1
}
return rh + 1
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isBalanced(TreeNode* root) {
return height(root) != -1;
}
private:
int height(TreeNode* node) {
if (!node) return 0;
int lh = height(node->left);
if (lh == -1) return -1;
int rh = height(node->right);
if (rh == -1) return -1;
if (abs(lh - rh) > 1) return -1;
return max(lh, rh) + 1;
}
};# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isBalanced(self, root) -> bool:
return self.height(root) != -1
def height(self, node):
if not node:
return 0
lh = self.height(node.left)
if lh == -1:
return -1
rh = self.height(node.right)
if rh == -1:
return -1
if abs(lh - rh) > 1:
return -1
return max(lh, rh) + 1/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
var isBalanced = function(root) {
return height(root) !== -1;
};
function height(node) {
if (node === null) return 0;
const lh = height(node.left);
if (lh === -1) return -1;
const rh = height(node.right);
if (rh === -1) return -1;
if (Math.abs(lh - rh) > 1) return -1;
return Math.max(lh, rh) + 1;
}
Comments