深度优先遍历 DFS
解题思路
方式一：自底向上递归的做法类似于后序遍历，将后面的结果一层一层向上返回 ，对于当前遍历到的节点，先递归地判断其左右子树是否平衡，再判断以当前节点为根的子树是否平衡；
- 如果一棵子树是平衡的，则返回其高度（高度一定是非负整数），否则返回 -1；
- 如果存在一棵子树不平衡，则整个二叉树一定不平衡；
方式二：求出最大深度和最小深度，比较之间差值是否大于一，此种方式行不通，如果二叉树退化成链表后，最大深度和最小深度相同；
复杂度
-
时间复杂度：
O(n)，其中 n 是二叉树中的节点个数；使用自底向上的递归，每个节点的计算高度和判断是否平衡都只需要处理一次，最坏情况下需要遍历二叉树中的所有节点，因此时间复杂度是O(n)； -
空间复杂度：
O(n)，其中 n 是二叉树中的节点个数；空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过 n；
代码实现
var isBalanced = function (root) {
return getHeight(root) !== -1;
}
const getHeight = (node) => {
if (node === null) return 0;
// 左子树的高度
const leftH = getHeight(node.left);
if (leftH === -1) return -1; // 左子树不满足平衡二叉树，提前退出，不再递归
// 右子树的高度
const rightH = getHeight(node.right);
if (rightH === -1) return -1; // 右子树不满足平衡二叉树，提前退出，不再递归
// 根据左子树和右子树的高度差，判断当前数是否是平衡二叉树
if (Math.abs(leftH - rightH) > 1) return -1;
// 当前节点的高度
return Math.max(leftH, rightH) + 1;
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 71. 简化路径
上一篇
评论
