残缺高频题库仓库地址：https://github.com/hzfe/aweso...

残缺高频题库浏览地址：https://febook.hzfe.org/

题目形容

输出一棵二叉树的根节点，判断该树是不是均衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过 1，那么它就是一棵均衡二叉树。

示例 1:

给定二叉树 [3, 9, 20, null, null, 15, 7]    3   / \  9  20    /  \   15   7返回 true。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]       1      / \     2   2    / \   3   3  / \ 4   4返回 false。

限度：0 <= 树的结点个数 <= 10000

根本知识点

二叉树的每个节点最多有两个子节点，均衡二叉树中任意一个节点的左右子树高度相差不能大于 1，满二叉树和齐全二叉树都是均衡二叉树，一般二叉树有可能是均衡二叉树。

题解

解法一

思路

若想判断二叉树是不是均衡二叉树，只须要判断左右子树的高度差是不是不超过 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) * } *//** * @param {TreeNode} root * @return {boolean} */const isBalanced = function (root) {  if (root === null) {    return true;  } else {    return (      Math.abs(height(root.left) - height(root.right)) <= 1 &&      isBalanced(root.left) &&      isBalanced(root.right)    );  }};const height = function (root) {  if (root === null) {    return 0;  } else {    return Math.max(height(root.left), height(root.right)) + 1;  }};

工夫复杂度剖析

该办法最坏的状况是每个父节点都只有一个子节点，这样树的高度工夫复杂度为 O(n)，即“链表”的长度。而第 d 层调用 height 函数的工夫复杂度是 O(d)，所以整体的工夫复杂度为高度工夫复杂度 * 调用 height 函数的工夫复杂度，即 O(n^2)。

空间复杂度剖析

该办法因为应用了递归，并且每次递归都调用了两次本身，导致会函数栈会依照等差数列开拓，所以该办法的空间复杂度应为 O(n^2)。

解法二

思路

下面的办法是自顶而上的，这样其实就会导致每层的高度都要反复计算。那么，咱们能够应用后序遍历，这样每个节点的高度就能依据后面的后果算进去。

代码

/** * 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) * } *//** * @param {TreeNode} root * @return {boolean} */var isBalanced = function (root) {  return height(root) != -1;};var height = function (root) {  if (root == null) {    return 0;  }  const left = height(root.left);  const right = height(root.right);  if (left === -1 || right === -1 || Math.abs(left - right) > 1) {    return -1;  }  return Math.max(left, right) + 1;};

工夫复杂度剖析

因为是后序遍历，每个节点只会被调用 1 次，所以，该办法的工夫复杂度是 O(n)。

空间复杂度剖析

该办法因为应用了递归，并且每次递归都调用了两次本身，导致会函数栈会依照等差数列开拓，所以该办法的空间复杂度应为 O(n^2)。