平衡二叉树#
题目描述#
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过 1，那么它就是一棵平衡二叉树。
示例 1:
1给定二叉树 [3, 9, 20, null, null, 15, 7]
2
3 3
4 / \
5 9 20
6 / \
7 15 7
8返回 true。示例 2:
1给定二叉树 [1,2,2,3,3,null,null,4,4]
2
3 1
4 / \
5 2 2
6 / \
7 3 3
8 / \
9 4 4
10返回 false。限制：0 <= 树的结点个数 <= 10000
基本知识点#
二叉树的每个节点最多有两个子节点，平衡二叉树中任意一个节点的左右子树高度相差不能大于 1，满二叉树和完全二叉树都是平衡二叉树，普通二叉树有可能是平衡二叉树。
题解#
解法一#
思路#
若想判断二叉树是不是平衡二叉树，只需要判断左右子树的高度差是不是不超过 1 即可。同时，要满足一个树是平衡二叉树，它的子树也必须是平衡二叉树。我们可以从根结点开始，通过递归来求得子树的高度，以及子树是否是平衡二叉树，以此来结合判断二叉树是否是平衡二叉树。
代码#
1/**
2 * Definition for a binary tree node.
3 * function TreeNode(val, left, right) {
4 * this.val = (val === undefined ? 0 : val)
5 * this.left = (left === undefined ? null : left)
6 * this.right = (right === undefined ? null : right)
7 * }
8 */
9/**
10 * @param {TreeNode} root
11 * @return {boolean}
12 */
13const isBalanced = function (root) {
14 if (root === null) {
15 return true;
16 } else {
17 return (
18 Math.abs(height(root.left) - height(root.right)) <= 1 &&
19 isBalanced(root.left) &&
20 isBalanced(root.right)
21 );
22 }
23};
24
25const height = function (root) {
26 if (root === null) {
27 return 0;
28 } else {
29 return Math.max(height(root.left), height(root.right)) + 1;
30 }
31};时间复杂度分析#
该方法最坏的情况是每个父节点都只有一个子节点，这样树的高度时间复杂度为 O(n)，即“链表”的长度。而第 d 层调用 height 函数的时间复杂度是 O(d)，所以整体的时间复杂度为高度时间复杂度 * 调用 height 函数的时间复杂度，即 O(n^2)。
空间复杂度分析#
空间复杂度取决于递归调用的层数，不会超过 n 层，所以空间复杂度是 O(n)。
解法二#
思路#
上面的方法是自顶而下的，这样其实就会导致每层的高度都要重复计算。那么，我们可以使用后序遍历，这样每个节点的高度就能根据前面的结果算出来。
代码#
1/**
2 * Definition for a binary tree node.
3 * function TreeNode(val, left, right) {
4 * this.val = (val === undefined ? 0 : val)
5 * this.left = (left === undefined ? null : left)
6 * this.right = (right === undefined ? null : right)
7 * }
8 */
9/**
10 * @param {TreeNode} root
11 * @return {boolean}
12 */
13var isBalanced = function (root) {
14 return height(root) != -1;
15};
16
17var height = function (root) {
18 if (root == null) {
19 return 0;
20 }
21
22 const left = height(root.left);
23 const right = height(root.right);
24
25 if (left === -1 || right === -1 || Math.abs(left - right) > 1) {
26 return -1;
27 }
28
29 return Math.max(left, right) + 1;
30};时间复杂度分析#
由于是后序遍历，每个节点只会被调用 1 次，所以，该方法的时间复杂度是 O(n)。
空间复杂度分析#
空间复杂度取决于递归调用的层数，不会超过 n 层，所以空间复杂度是 O(n)。
目录