🌴 平衡二叉树

📝 题目描述

​ 给定一个二叉树，判断它是否是平衡二叉树。平衡二叉树是指该树所有节点的左右子树的高度之差的绝对值不超过1。

📋 代码模板

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {

    }
}

typescript

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function isBalanced(root: TreeNode | null): boolean {
    
}

💡 提示

1. 树中的节点数在范围 $[0,5000]$ 内
2. $-{10}^4<=Node.val<={10}^4$

🚀 示例

🖊️ 题解

前序遍历

可惜没有如果

java

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);
    }

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

typescript

后序遍历

可惜没有如果

java

class Solution {
    private final static int FLAG = -1;

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

    public int height(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int leftHeight = height(node.left);
        if (leftHeight == FLAG) {
            return FLAG;
        }
        int rightHeight = height(node.right);
        if (rightHeight == FLAG || Math.abs(leftHeight - rightHeight) > 1) {
            return FLAG;
        }
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

typescript

const FLAG = -1;

function isBalanced(root: TreeNode | null): boolean {
    return height(root) != FLAG;
}

function height(node: TreeNode | null): number {
    if (node == null) {
        return 0;
    }
    const leftHeight = height(node.left);
    if (leftHeight == FLAG) {
        return -1;
    }
    const rightHeight = height(node.right);
    if (rightHeight == FLAG || Math.abs(leftHeight - rightHeight) > 1) {
        return -1;
    }
    return Math.max(leftHeight, rightHeight) + 1;
}

💭 复杂度分析