#104. Maximum Depth of Binary Tree

題目描述

給你一個二元樹的起點，回傳樹的最大深度。

二元樹的最大深度是從根節點到最遠的葉節點所經過的節點數量。

限制條件

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

解題思路

這一題最直覺最快速的解法就是使用深度優先搜尋(DFS)。

深度優先搜尋 DFS

public class Solution { 
	public int MaxDepth(TreeNode root) {
        if(root==null) return 0;
        return 1+Math.Max(MaxDepth(root.left),MaxDepth(root.right));
    }
}

複雜度分析：

• 時間複雜度：每個節點都必須檢查過一次，因此時間複雜度為O(n)。
• 空間複雜度：要等到所有節點都堆疊完後才會開始回傳，因此空間複雜度為O(n)。

學習重點

• 深度優先搜尋 DFS