題目資訊

• 題目編號: 1261
• 題目連結: Find Elements in a Contaminated Binary Tree
• 主題: Hash Table, Tree, Depth-First Search, Breadth-First Search, Design, Binary Tree

題目敘述

給定一個二元樹，並遵循以下規則：

1. root.val == 0
2. 對於任何 treeNode:
   • 如果 treeNode.val 的值為 $x$ 且 treeNode.left != null，那麼 treeNode.left.val == 2 * x + 1
   • 如果 treeNode.val 的值為 $x$ 且 treeNode.right != null，那麼 treeNode.right.val == 2 * x + 2

現在這棵二元樹被污染，這意味著所有的 treeNode.val 都已被改為 -1。

實作 FindElements 類別：

• FindElements(TreeNode* root) 使用污染的二元樹初始化物件並恢復它。
• bool find(int target) 如果恢復的二元樹中存在 target 值，則返回 true。

範例 1:

輸入
[“FindElements”,“find”,“find”]
[[[-1,null,-1]],[1],[2]]

輸出
[null,false,true]

解釋
FindElements findElements = new FindElements([-1,null,-1]);
findElements.find(1); // 返回 False
findElements.find(2); // 返回 True

範例 2:

輸入
[“FindElements”,“find”,“find”,“find”]
[[[-1,-1,-1,-1,-1]],[1],[3],[5]]

輸出
[null,true,true,false]

解釋
FindElements findElements = new FindElements([-1,-1,-1,-1,-1]);
findElements.find(1); // 返回 True
findElements.find(3); // 返回 True
findElements.find(5); // 返回 False

範例 3:

輸入
[“FindElements”,“find”,“find”,“find”,“find”]
[[[-1,null,-1,-1,null,-1]],[2],[3],[4],[5]]

輸出
[null,true,false,false,true]

解釋
FindElements findElements = new FindElements([-1,null,-1,-1,null,-1]);
findElements.find(2); // 返回 True
findElements.find(3); // 返回 False
findElements.find(4); // 返回 False
findElements.find(5); // 返回 True

約束條件：

• TreeNode.val == -1
• 二元樹的高度小於或等於 $20$
• 節點總數在 $[1, 10^4]$ 之間
• find() 的總呼叫次數在 $[1, 10^4]$ 之間
• $0 \leq target < 10^6$

直覺

此問題涉及復原一棵已被汙染的二叉樹，所有節點的值皆初始化為 -1。樹依據特定規則形成特定的結構。為了有效地判斷目標值是否存在於這棵復原後的二叉樹中，我們需要一種利用二叉樹特性的策略。這裡的關鍵觀察是，如果我們能以某種形式復原這棵樹，那麼檢查某個目標是否存在，就變成確認它是否屬於這個結構的問題。

解法

解決此問題的策略包括以下步驟：

1. 樹的復原: 首先，我們需要依據給定的規則重建二叉樹：

   • 以根節點開始，根節點的值應定義為 0。
   • 對於位於位置 $x$ 的每個節點，其左子節點的值為 $2x + 1$，右子節點的值為 $2x + 2$。

   我們使用遞迴方法 recoverTree 來實現這個目標。從索引為 0 的根節點開始，遞迴地根據以上公式設置子節點的值。在此過程中，我們也將復原的值存儲在一個集合中，以便高效查找操作。

2. 高效查找: 為了有效地檢查目標值是否存在於復原的樹中，我們維護了一個包含所有復原值的集合。方法 find 實質上是在檢查目標是否存在於此集合中。由於基於哈希的集合具備特性，這提供了平均時間複雜度為 $O(1)$ 的查找操作。

3. 實施細節:

   • recoverTree 函數負責根據樹結構規則為每個節點賦予正確的值。
   • FindElements 構造函數初始化此復原過程，確保當物件一創建時，二叉樹即被重建。
   • find 函數然後利用預先填充的復原值集合來確定給定目標是否在樹中存在。

透過利用此特定基於規則的樹結構特性，以及高效地存儲復原值，我們在重建和搜索方面皆達到最優化。

程式碼

C++

/**
 * 二叉樹節點的定義。
 */
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 FindElements {
public:
    // 用來儲存復原後節點值的集合。
    set<int> recoveredValues;

    // 幫助復原二叉樹的輔助函數。
    void recoverTree(TreeNode* root, int index) {
        if (root == nullptr) return;

        // 插入當前節點計算出的索引值。
        recoveredValues.insert(index);

        // 遞迴復原左子節點。
        recoverTree(root->left, index * 2 + 1);

        // 遞迴復原右子節點。
        recoverTree(root->right, index * 2 + 2);
    }

    // 啟動二叉樹復原的建構子。
    FindElements(TreeNode* root) {
        // 從索引0（根節點）開始復原過程。
        recoverTree(root, 0);
    }
    
    // 方法用於查找目標值是否存在於復原後的樹中。
    bool find(int target) {
        // 檢查目標值是否在復原後的集合中。
        return recoveredValues.count(target);
    }
};

/**
 * 你的 FindElements 物件將以這樣的方式進行實例化和調用：
 * FindElements* obj = new FindElements(root);
 * bool param_1 = obj->find(target);
 */

Python

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

class FindElements:
    # 用於儲存回復後節點值的集合。
    def __init__(self, root: TreeNode):
        self.recoveredValues = set()
        
        # 從索引 0 (根節點) 開始回復過程。
        self.recoverTree(root, 0)
    
    # 回復二元樹的輔助函數。
    def recoverTree(self, root: TreeNode, index: int):
        if root is None:
            return
        
        # 插入當前節點的計算索引值。
        self.recoveredValues.add(index)
        
        # 遞歸地回復左子節點。
        self.recoverTree(root.left, index * 2 + 1)
        
        # 遞歸地回復右子節點。
        self.recoverTree(root.right, index * 2 + 2)
    
    # 方法去檢查目標是否存在於回復後的樹中。
    def find(self, target: int) -> bool:
        # 檢查目標是否在已回復的值集合中。
        return target in self.recoveredValues

# 您的 FindElements 對象將被實例化並如此使用：
# obj = FindElements(root)
# param_1 = obj.find(target)

複雜度分析

• 時間複雜度: $O(n + m \log n)$
• 空間複雜度: $O(n)$