Eisen 筆記

#543. Diameter of Binary Tree

題目描述

給你二元樹的起點root，回傳樹的直徑。

樹的直徑的定義是二元樹的其中兩個節點之間存在著的最長路徑。這個路徑有可能不會通過二元樹的起點。

兩點之間的路徑的長度用經過的節點之間的連線表示。

限制條件

  1. 節點數量為[1,10^4]。
  2. -100 <= 節點值 <= 100
  3. 最長路徑有可能不會通過起點。

解題思路

二元樹中一個節點的最長路徑，一般是左子節點深度和右子節點深度的總和。 但這一題要注意的是，最長路徑有可能不會通過起點。 那最直覺的方式就是檢查每個節點的深度，然後回傳最長的深度總和。

遞迴 Recursion

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

複雜度分析：

  • 時間複雜度：一共有n個節點，每一個節點都會呼叫計算深度的函式，因此計算深度的函式至少會被呼叫n次，而計算深度函式每往下一層所需要的計算時間都會比前一次少一半，但是同一層呼叫的函式數量會多一倍，一加一減之下，每一層花費的時間都差不多，因此最差會花上n/2也就是總層數的時間，所以時間複雜度為 O(n^2)。
  • 空間複雜度：遞迴會堆疊n個節點，而計算深度也會堆疊n個節點，因此空間複雜度是O(n^2)。

改進 Improve

承上，上一個解法雖然很明確，先檢查每一個點，然後每一個點都做一次深度查詢，找出最長的路徑，但還有可以改進的空間。
計算深度的函式，在計算深度的同時，本身就需要去檢查每一個節點，等於跟檢查每個節點重複了，因此浪費了較多了時間。
所以我們只要在檢查深度的時候，順便把每個節點的深度加總起來，就可以得到那個節點的最長路徑長度了，再來就是使用一個外部變數把最長的路徑記錄下來，就可以回傳答案了。

public class Solution {
	int ans = 0;
    public int DiameterOfBinaryTree(TreeNode root) {        
        Depth(root);
        return ans;
    }
    public int Depth(TreeNode root){
        if(root==null) return -1;
        int left = Depth(root.left);
        int right = Depth(root.right);
        ans = Math.Max(ans,2+left+right);
        return 1+Math.Max(left,right);
    }
}
  • 時間複雜度：由於要檢查每個節點，因此時間複雜度為O(n)。
  • 空間複雜度：遞迴會堆疊n個節點，因此空間複雜度是O(n)。

學習重點

  • 二元樹
  • 遞迴
  • 深度優先搜尋
Last Updated:
Contributors: eisen