LeetCode110——平衡二叉樹

我的LeetCode代碼倉：https://github.com/617076674/LeetCode

原題連結：https://leetcode-cn.com/problems/balanced-binary-tree/description/

題目描述：

知識點：遞歸、樹的層序周遊

思路：遞歸判斷該樹是否是高度平衡的二叉樹

遞歸終止條件：

（1）如果root為null，傳回true。

（2）如果root的左子樹和右子樹的高度差超過1，傳回false。

遞歸過程：

如果不滿足2種遞歸終止條件，隻有當其左子樹和右子樹均是平衡二叉樹時，才能傳回true。這就遞歸調用了原函數。

至于如何求樹的高度，可以層序周遊求解，層序周遊的方法和LeetCode102——二叉樹的層序周遊中的思路相同。

時間複雜度是O(n * h)，其中n是二叉樹的節點個數，h是二叉樹的高度。空間複雜度是O(h)。

JAVA代碼：

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

    private int calculateDepth(TreeNode node) {
        if(node == null) {
            return 0;
        }
        int levelCount = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(node);
        while(!queue.isEmpty()) {
            int level = queue.size();
            levelCount++;
            while(level > 0) {
                level--;
                TreeNode temp = queue.poll();
                if(temp.left != null) {
                    queue.add(temp.left);
                }
                if(temp.right != null) {
                    queue.add(temp.right);
                }
            }
        }
        return levelCount;
    }
}
           

LeetCode解題報告：