110. Balanced Binary Tree - Easy

前往題目

這題也是做過的

心得

• 這題的考點就是如何有效遍歷
• 想了十分鐘，曾經有想過484直接用遞迴然後紀錄每個節點的高度
• 因為想不出來怎麼實作，於是直接看解答，還真的是我想的這個樣子
• 結論就是對於遞迴還不是非常熟

思路

1. 樹遞迴每個節點
2. 紀錄left和right的高度
3. 比較每個左子樹以及右子樹的高度，如果大於1那整個tree就不是balanced binary tree

Code

private boolean result = true;

public boolean isBalanced(TreeNode root) {
    maxDepth(root);
    return result;
}

public int maxDepth(TreeNode root){
    if(root == null){
        return 0;
    }

    int l = maxDepth(root.left); //Store the max depth of left subtree
    int r = maxDepth(root.right); // Store the max depth of right subtree

    if(Math.abs(l - r) > 1){
        result = false;
    }

    return 1 + Math.max(l, r);
}

2023/12/13

嘗試再做一次，核心想法的部分有想出來，但寫recursion還是會卡住，再看一次code覺得非常有邏輯，不知道下次腦袋轉不轉得過來