題目資訊

題目編號: 865
題目連結: Smallest Subtree with all the Deepest Nodes
主題: Hash Table, Tree, Depth-First Search, Breadth-First Search, Binary Tree

題目敘述

給定二元樹的 root，每個節點的深度是到根的最短距離。

返回最小的子樹，該子樹包含原始樹中所有最深的節點。

如果一個節點在整棵樹中擁有最大的可能深度，則稱其為最深的。

一個節點的子樹是一棵由該節點加上其所有後代組成的樹。

範例 1:

範例 1

輸入: root = [3,5,1,6,2,0,8,null,null,7,4]
輸出: [2,7,4]
解釋: 我們返回圖中以黃色標示的值為 2 的節點。
藍色標示的節點是樹中最深的節點。
注意節點 5、3 和 2 包含了樹中最深的節點，但節點 2 是它們之中最小的子樹，因此我們返回它。

範例 2:

輸入: root = [1]
輸出: [1]
解釋: 根節點是樹中最深的節點。

範例 3:

輸入: root = [0,1,3,null,2]
輸出: [2]
解釋: 樹中最深的節點是 2，合理的子樹有節點 2、1 和 0 的子樹，但節點 2 的子樹是最小的。

約束條件:

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

注意: 這個問題與 1123 題相同: https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/

直覺

本問題要求識別在一個給定的二叉樹中包含所有最深節點的最小子樹。一個直接的方法是使用深度優先搜索（DFS）來遍歷二叉樹，收集每個節點的深度信息。通過確定最深的節點並評估樹的結構，我們可以有效地找到所需的子樹。關鍵的見解在於識別包圍所有最深節點的子樹，這相當於找到這些節點的最低共同祖先（LCA）。

解法

該算法採用了深度優先搜索（DFS）來分析這個二叉樹。主要的挑戰在於找到包含所有具有最大深度的節點的最小子樹。遞歸的DFS函數執行以下步驟：

基礎情況：如果節點是 nullptr，則返回由 nullptr 和深度 0 組成的一對，表示該位置缺乏節點。
遞歸搜索：對於每一個節點，遞歸地調用DFS函數對其左子節點和右子節點進行計算，並以一對形式獲取其最深節點及其深度信息。
深度比較：
- 如果左子樹包含的最深節點的深度大於右子樹，則返回來自左子樹的數據，並增加一以計入當前節點的深度。
- 反之，若右子樹的深度更大，則返回來自右子樹的數據，並同樣增加一。
- 如果左右子樹的深度相等，這意味著當前節點是來自兩個子樹中最深節點的共同祖先。返回當前節點及其深度。
解的提取：從根節點開始進行DFS遍歷。此遍歷返回的節點代表了包含所有最深節點的最小子樹的根。

此方法通過評估子樹的深度並利用二叉樹的特性高效地確定所需子樹的位置和存在。

程式碼

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) {
        // 基本情況：如果當前節點為空，返回一個空指針及深度0的組合。
        if (node == nullptr) return {nullptr, 0};
        
        // 以遞迴方式計算左子樹和右子樹的最深節點信息。
        pair<TreeNode*, int> left_info = dfs(node->left);
        pair<TreeNode*, int> right_info = dfs(node->right);
        
        // 比較左右子樹的深度。
        if (left_info.second > right_info.second)
            return {left_info.first, left_info.second + 1};  // 左子樹較深。
        else if (left_info.second < right_info.second)
            return {right_info.first, right_info.second + 1}; // 右子樹較深。
        else
            return {node, left_info.second + 1}; // 兩個子樹深度相同。
    }

    // 找到包含所有最深節點的最小子樹的函式。
    TreeNode* subtreeWithAllDeepest(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):
        # 基本情況：如果當前節點為空，返回一個None和深度0的元組。
        if node is None:
            return (None, 0)
        
        # 遞迴計算左右子樹中最深節點的信息。
        left_info = self.dfs(node.left)
        right_info = self.dfs(node.right)
        
        # 比較左右子樹的深度。
        if left_info[1] > right_info[1]:
            return (left_info[0], left_info[1] + 1)  # 左子樹較深。
        elif left_info[1] < right_info[1]:
            return (right_info[0], right_info[1] + 1) # 右子樹較深。
        else:
            return (node, left_info[1] + 1) # 兩個子樹深度相同。

    # 函數用於找到包含所有最深節點的最小子樹。
    def subtreeWithAllDeepest(self, root):
        return self.dfs(root)[0]

複雜度分析

時間複雜度: $O(n)$
給定的解決方案涉及二元樹的深度優先搜尋（DFS）遍歷。樹中的每個節點都會被訪問一次以計算深度並確定最深的子樹。因此，時間複雜度為 $O(n)$，其中 $n$ 是樹中節點的數量。
空間複雜度: $O(h)$
空間複雜度由 DFS 遍歷中使用的遞迴堆疊決定。在最壞情況下，樹的高度可能是 $n$（例如一棵偏斜樹），導致空間複雜度為 $O(n)$。然而，對於一棵平衡樹，高度為 $O(\log n)$。因此，空間複雜度為 $O(h)$，其中 $h$ 是樹的高度。

CS Note
En

Leetcode 865. Smallest Subtree with all the Deepest Nodes

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析