给定一棵二叉树，判断它是否是高度平衡的（深度差不大于 1）（leetcode 110）

Question

在学习解决这个问题的过程中，我遇到了 2 个解决方案，但我无法理解它们的时间复杂度，请教我如何去做。

Sol 1：O(n) - 后序 DFS 以找到每个节点的高度

var isBalanced = function(root) {

let dfs = function(node) {
    if (!node) return 0;
    let left = 1 + dfs(node.left);
    let right = 1 + dfs(node.right);
    if (Math.abs(left - right) > 1) return Infinity;
    return Math.max(left, right);
}

return dfs(root)==Infinity?false:true;
};

Sol 2：O(n^2)- 标准自上而下递归

var isBalanced = function(root) {
if (!root) return true;

let height = function(node) {
    if (!node) return 0;
    return 1 + Math.max(height(node.left), height(node.right));
}

return Math.abs(height(root.left) - height(root.right)) < 2 && isBalanced(root.left) && isBalanced(root.right);
 };

Answer 1

你得问问自己你的算法访问了多少个节点。

解决方案 1 是深度优先搜索，它只访问每个节点一次。其余的是恒定时间操作。因此，如果您的树中有 n 个节点，则复杂度为 O(n).

解决方案 2 是访问每个节点，但对于每次访问，它会访问其每个子节点。因此，复杂度为O(n * n) = O(n²).

给定一棵二叉树，判断它是否是高度平衡的（深度差不大于 1）（leetcode 110）

Given a binary tree, determine if it is height-balanced(difference in depth is not mroe than 1) (leetcode 110)

javascript

data-structures

time-complexity

binary-search-tree

depth-first-search