110. 平衡二叉树

题目描述

输入二叉树的根节点 root，判断它是否为高度平衡的二叉树。

高度平衡的意思是：树中任何一个节点，其左子树与右子树的高度之差的绝对值都不超过 1。

是则返回 true，否则返回 false。空树视为平衡。树用层序数组表示，null 代表空位。

示例 1

输入：root = [3,9,20,null,null,15,7]
输出：true

解释：根的左子树高 1、右子树高 2，其余节点也都满足条件。

示例 2

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

解释：根的左子树高 3，右子树高 1，相差 2。

示例 3

输入：root = []
输出：true

解释：空树是平衡的。

数据范围

节点总数在 [0, 5000] 之间。
-10^4 <= Node.val <= 10^4

解题思路：自底向上递归

自底向上计算高度。height(node) 后序遍历：先求左子树高度，再求右子树高度，然后检查差值。一旦发现某棵子树不平衡，就返回 -1 作为标记，上层看到 -1 直接继续返回 -1，不再做多余计算。这样每个节点只访问一次。

为什么正确

height(node) 返回非负数时，这棵子树已经平衡且该数就是高度；返回 -1 表示子树内某处不平衡。

复杂度分析

时间 O(n)，空间 O(h)，h 为树高（递归栈）。

易错点

只比较根节点左右子树的高度是不够的，每个节点都要满足。另外自顶向下对每个节点重新算高度会变成 O(n^2)。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def height(node):
            if not node:
                return 0
            lh = height(node.left)
            if lh == -1:
                return -1
            rh = height(node.right)
            if rh == -1 or abs(lh - rh) > 1:
                return -1
            return max(lh, rh) + 1
        return height(root) != -1

class Solution {
    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 || Math.abs(lh - rh) > 1) {
            return -1;
        }
        return Math.max(lh, rh) + 1;
    }

    public boolean isBalanced(TreeNode root) {
        return height(root) != -1;
    }
}

class Solution {
public:
    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 || abs(lh - rh) > 1) {
            return -1;
        }
        return max(lh, rh) + 1;
    }
    bool isBalanced(TreeNode* root) {
        return height(root) != -1;
    }
};

func isBalanced(root *TreeNode) bool {
	var height func(node *TreeNode) int
	height = func(node *TreeNode) int {
		if node == nil {
			return 0
		}
		lh := height(node.Left)
		if lh == -1 {
			return -1
		}
		rh := height(node.Right)
		if rh == -1 || lh-rh > 1 || rh-lh > 1 {
			return -1
		}
		return max(lh, rh) + 1
	}
	return height(root) != -1
}

var isBalanced = function(root) {
    const height = (node) => {
        if (!node) {
            return 0;
        }
        const lh = height(node.left);
        if (lh === -1) {
            return -1;
        }
        const rh = height(node.right);
        if (rh === -1 || Math.abs(lh - rh) > 1) {
            return -1;
        }
        return Math.max(lh, rh) + 1;
    };
    return height(root) !== -1;
};

function isBalanced(root: TreeNode | null): boolean {
    const height = (node: TreeNode | null): number => {
        if (!node) {
            return 0;
        }
        const lh = height(node.left);
        if (lh === -1) {
            return -1;
        }
        const rh = height(node.right);
        if (rh === -1 || Math.abs(lh - rh) > 1) {
            return -1;
        }
        return Math.max(lh, rh) + 1;
    };
    return height(root) !== -1;
}

载入编辑器，自己跑一遍 →

其他解法

自顶向下按定义逐层检查，高度反复计算；自底向上在求高度的同时判断平衡，用 -1 提前剪枝，每个节点只访问一次。

解法 2：自顶向下递归时间 O(n²)，空间 O(h)

先写一个普通的 height 函数求子树高度。对当前节点，检查左右子树高度差不超过 1，再递归判断左子树和右子树都平衡。

直接照着定义写，容易想到。同一个节点的高度会被重复计算，最坏 O(n²)；平衡树上是 O(n log n)。

class Solution:
    def isBalanced(self, root):
        def height(node):
            if not node:
                return 0
            return max(height(node.left), height(node.right)) + 1
        if not root:
            return True
        return (abs(height(root.left) - height(root.right)) <= 1
                and self.isBalanced(root.left) and self.isBalanced(root.right))

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        return Math.abs(height(root.left) - height(root.right)) <= 1
            && isBalanced(root.left) && isBalanced(root.right);
    }

    private int height(TreeNode node) {
        if (node == null) return 0;
        return Math.max(height(node.left), height(node.right)) + 1;
    }
}

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if (!root) return true;
        return abs(height(root->left) - height(root->right)) <= 1
            && isBalanced(root->left) && isBalanced(root->right);
    }

    int height(TreeNode* node) {
        if (!node) return 0;
        return max(height(node->left), height(node->right)) + 1;
    }
};

func isBalanced(root *TreeNode) bool {
	if root == nil {
		return true
	}
	d := height(root.Left) - height(root.Right)
	return d >= -1 && d <= 1 && isBalanced(root.Left) && isBalanced(root.Right)
}

func height(node *TreeNode) int {
	if node == nil {
		return 0
	}
	return max(height(node.Left), height(node.Right)) + 1
}

var isBalanced = function(root) {
    const height = (node) => node ? Math.max(height(node.left), height(node.right)) + 1 : 0;
    if (!root) return true;
    return Math.abs(height(root.left) - height(root.right)) <= 1
        && isBalanced(root.left) && isBalanced(root.right);
};

function isBalanced(root: TreeNode | null): boolean {
    const height = (node: TreeNode | null): number => node ? Math.max(height(node.left), height(node.right)) + 1 : 0;
    if (!root) return true;
    return Math.abs(height(root.left) - height(root.right)) <= 1
        && isBalanced(root.left) && isBalanced(root.right);
};

二叉树专题的其他题目

查看二叉树全部题目 →