#110. Balanced Binary Tree

題目描述

給你一個二元樹，判斷是否為高度平衡樹。

高度平衡樹指的是二元樹左右的每一個節點深度差不會大於1。

限制條件

1. 節點數量範圍為[0, 5000]。
2. -10^4 <= 節點值 <= 10^4

解題思路

這一題有兩個條件要考慮：

1. 深度不會大於1。
2. 每一個節點都高度平衡。

然後是解決問題的步驟：

1. 需要先找出深度。
2. 比較深度，判斷是否高度平衡。
3. 每一個節點都要檢查。

Solution

public class Solution {
	public bool IsBalanced(TreeNode root) {
		// Edge Case
        if(root==null) return true;
		// Get Depth & Compare Depth
        if(Math.Abs(Depth(root.left)-Depth(root.right))>1) return false;
		// Check Every Nodes.
        return IsBalanced(root.left)&&IsBalanced(root.right);
    }
    public int Depth(TreeNode root){
        if(root==null) return 0;
        return 1+Math.Max(Depth(root.left),Depth(root.right));
    }
}

複雜度分析：

• 時間複雜度：每一多一個節點，深度查詢的呼叫次數就會變成n^2，所以時間複雜度為O(n^2)。
• 空間複雜度：由於使用遞迴來尋找深度，最多會檢查所有的節點，也就是N個節點，因此空間複雜度為O(n)。

學習重點