題目資訊

題目編號: 1123
題目連結: Lowest Common Ancestor of Deepest Leaves
主題: Hash Table, Tree, Depth-First Search, Breadth-First Search, Binary Tree

題目敘述

給定一個二叉樹的 root，返回其 最深葉子節點的最低共同祖先。

回顧概念：

當且僅當一個二叉樹的節點沒有子節點時，它才是葉子節點
樹的根節點的深度為 $0$。如果一個節點的深度為 $d$，則其每個子節點的深度為 $d + 1$。
節點集合 $S$ 的最低共同祖先是深度最大的那個節點 $A$，使得 $S$ 中的每個節點都在以 $A$ 為根的子樹中。

範例 1:

Example 1

輸入：root = [3,5,1,6,2,0,8,null,null,7,4]
輸出：[2,7,4]
解釋：我們返回圖中以黃色標示的值為 2 的節點。
藍色標示的節點是樹中最深的葉子節點。
注意，節點 6、0 和 8 也是葉子節點，但它們的深度為 2，而節點 7 和 4 的深度為 3。

範例 2:

輸入：root = [1]
輸出：[1]
解釋：根節點是樹中最深的節點，也是它自身的最低共同祖先。

範例 3:

輸入：root = [0,1,3,null,2]
輸出：[2]
解釋：樹中最深的葉子節點是 2，單個節點的最低共同祖先是它自身。

限制條件：

樹中節點的數量範圍是 $[1, 1000]$。
$0 \leq \text{Node.val} < 1000$
樹中節點的值是 唯一的。

注意： 這個問題與題目 865 相同：https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/

直覺

為了解決在二元樹中尋找最深葉結點的最低共同祖先（LCA）這一問題，我們需要理解兩個關鍵點：

最深的結點是那些位於樹之最大深度的結點。
一組結點的最低共同祖先是距離所有這些結點最近且能覆蓋它們的最深結點。

根據這些需求，一個自然的方法是遍歷樹以測量每個結點的深度，然後針對最深的結點確定其最低共同祖先。

解法

該演算法使用遞迴的深度優先搜尋（DFS）來遍歷樹並計算每個結點的深度。以下是逐步的解釋：

基礎情況：如果當前結點為 null，返回一個包含 nullptr 和深度 0 的配對。這表明我們已經達到樹的一端。
遞迴情況：
- 在當前結點的左子結點上執行 DFS，以獲取左子樹中最深結點及其深度。
- 同樣地，在右子結點上執行 DFS，以獲取右子樹中最深結點及其深度。
分析：
- 比較從左、右子樹獲得的深度：
  - 如果左子樹的深度較大，表示最深的結點位於左子樹中。因此，傳播左子樹的結果，並將深度增加 1 以考慮當前的結點。
  - 如果右子樹的深度較大，則最深的結點在右子樹中。同樣地，傳播右子樹的結果並將深度增加 1。
  - 如果兩個子樹的深度相同，意味著當前結點是兩邊最深結點的共同祖先。在這種情況下，將結果更新為當前結點並增加深度。
返回值：函數 lcaDeepestLeaves 從根結點開始啟動 DFS。DFS 函數返回一個配對，其中第一個元素為最深葉結點的最低共同祖先，第二個元素與輸出無關。主函數僅返回 LCA 結點。

此方法確保在完成後，我們識別出二元樹中最深結點的最低共同祖先。

程式碼

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    // 輔助函數，用於在樹上進行深度優先搜索
    pair<TreeNode*, int> dfs(TreeNode* node) {
        if (node == nullptr) {
            // 如果當前節點為空，返回 {nullptr, 0}
            return {nullptr, 0};
        }

        // 遞迴對左子樹和右子樹進行深度優先搜索
        pair<TreeNode*, int> leftResult = dfs(node->left);
        pair<TreeNode*, int> rightResult = dfs(node->right);

        // 比較左子樹和右子樹結果的深度
        if (leftResult.second > rightResult.second) {
            // 如果左子樹較深，傳遞左子樹結果並增加深度
            return {leftResult.first, leftResult.second + 1};
        } else if (leftResult.second < rightResult.second) {
            // 如果右子樹較深，傳遞右子樹結果並增加深度
            return {rightResult.first, rightResult.second + 1};
        } else {
            // 如果兩者深度相同，當前節點是共同祖先
            return {node, leftResult.second + 1};
        }
    }

    // 函數用於找到最深葉子節點的最近公共祖先
    TreeNode* lcaDeepestLeaves(TreeNode* root) {
        // 結果的第一項是最深葉子節點的最近公共祖先
        return dfs(root).first;
    }
};

Python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    # 協助函數以在樹上進行深度優先搜索
    def dfs(self, node):
        if node is None:
            # 如果當前節點為空，返回 (None, 0)
            return (None, 0)
        
        # 對左、右子樹進行遞迴深度優先搜索
        leftResult = self.dfs(node.left)
        rightResult = self.dfs(node.right)
        
        # 比較左、右子樹結果的深度
        if leftResult[1] > rightResult[1]:
            # 如果左子樹更深，傳遞左子樹結果並增加深度
            return (leftResult[0], leftResult[1] + 1)
        elif leftResult[1] < rightResult[1]:
            # 如果右子樹更深，傳遞右子樹結果並增加深度
            return (rightResult[0], rightResult[1] + 1)
        else:
            # 如果深度相同，則當前節點是共同祖先
            return (node, leftResult[1] + 1)

    # 找到最深葉子節點的最低共同祖先的函數
    def lcaDeepestLeaves(self, root):
        # 結果的第一項是最深葉子節點的LCA
        return self.dfs(root)[0]

複雜度分析

時間複雜度: $O(n)$
時間複雜度是 $O(n)$，因為在進行深度優先搜尋（DFS）時，二叉樹的每個節點恰好被訪問一次。在最壞的情況下，即當二叉樹是完全平衡的二叉樹時，DFS 將遍歷所有節點。因此，總共耗費的時間與樹中節點的數量（即 $n$）成正比。
空間複雜度: $O(h)$
空間複雜度是 $O(h)$，其中 $h$ 是二叉樹的高度。這是由於 DFS 函數的遞迴性質造成的。在最壞的情況下，空間複雜度由調用棧中中最大深度的函數調用決定，這對應於二叉樹的高度。對於平衡的二叉樹，高度 $h$ 約為 $O(\log n)$，但在最壞的情況下，即偏斜的二叉樹，其高度變為 $O(n)$。因此，一般來說，我們認為空間複雜度是 $O(h)$。

CS Note
En

Leetcode 1123. Lowest Common Ancestor of Deepest Leaves

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析