題目連結

題型解說

這是一題難度為簡單的題目

需要設計一個方法，此方法會傳入一個二元樹 root

回傳這棵樹是不是高度平衡，也就是左節點的深度與右節點點的深度相差不超過 1

解題思路

這題看是要寫個遞迴還是使用 Stack 搭配迴圈都可以

一開始做這一題時搞錯題意，原本以為只要從根節點算左右深度相減不超過 1 就好

結果是每一個節點左右都要平衡 Orz

程式碼

Java

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        
        if (Math.abs(isBalanced(root.left, 1) - isBalanced(root.right, 1)) > 1) {
            return false;
        }
        
        return isBalanced(root.left) && isBalanced(root.right);
    }
    
    public int isBalanced(TreeNode root, int nowLevel) {
        if (root == null) {
            return nowLevel -1;
        }
        
        return Math.max(isBalanced(root.left, nowLevel +1), isBalanced(root.right, nowLevel +1));
    }
}

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        
        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        
        while (!stack.empty()) {
            TreeNode node = stack.pop();
            int left = isBalanced(node.left, 1);
            int right = isBalanced(node.right, 1);
            
            // 找到一層不平衡就直接回傳
            if (Math.abs(left - right) > 1) {
                return false;
            }
            
            if (node.left != null) {
                stack.add(node.left);
            }
            
            if (node.right != null) {
                stack.add(node.right);
            }
        }
        
        return true;
    }
    
    public int isBalanced(TreeNode root, int nowLevel) {
        if (root == null) {
            return nowLevel -1;
        }
        
        return Math.max(isBalanced(root.left, nowLevel +1), isBalanced(root.right, nowLevel +1));
    }
}