🔗 🟡 2196. Create Binary Tree From Descriptions 1644

tags: `Weekly Contest 283` `陣列(Array)` `樹(Tree)` `二元樹(Binary Tree)` `雜湊表(Hash Table)`

題意

給定一個二維整數陣列 $\text{descriptions}$ ，當中 $\text{descriptions}[i] = [\text{parent}_i, \text{child}_i, \text{isLeft}_i]$ 表示 $\text{parent}_i$ 是 $\text{child}_i$ 在二元樹中的 父節點，且二元樹中所有節點的值都是唯一的。此外：

如果 $\text{isLeft}_i == 1$ ，則 $\text{child}_i$ 是 $\text{parent}_i$ 的左子節點。
如果 $\text{isLeft}_i == 0$ ，則 $\text{child}_i$ 是 $\text{parent}_i$ 的右子節點。

請根據 $\text{descriptions}$ 的描述來構造二元樹並返回其 根節點。

測試案例將保證生成的二元樹是 有效的。

思路：雜湊表(Hash Table)

由於我們從 $\text{descriptions}$ 中得到的資訊是以節點的值來描述的，因此我們可以使用一個雜湊表 $mp$ 來維護建立值與節點之間的對應關係。同時，為了找到根節點，我們還需要一個雜湊表 $pa$ 來記錄每個節點的父節點， $pa[v] = u$ 表示 $v$ 的父節點是 $u$ 。

具體步驟如下：

初始化兩個雜湊表 $mp$ 和 $pa$ ，分別用來存儲節點和父子關係。
遍歷 $\text{descriptions}$ $descriptions$ 陣列，對於每個描述 $[u, v, is\_left]$ $[u, v, i s_l e f t]$ ：
- 更新 $pa$ ，記錄 $v$ 的父節點是 $u$ 。
- 如果 $u$ 或 $v$ 不在 $mp$ 中，則創建對應的 TreeNode 並加入 $mp$ 。
- 根據 $is\_left$ 的值，將 $v$ 設置為 $u$ 的左子節點或右子節點。
找到根節點。根節點是沒有父節點的節點，因此我們從任意一個節點開始（這裡以第一個描述的父節點開始），沿著父節點的向上查找，直到找到一個沒有父節點的節點，即為根節點。
從 $mp$ 中取出根節點對應的 TreeNode，返回該節點。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ ，其中 $n$ 是 $\text{descriptions}$ 的長度。我們需要遍歷一次 $\text{descriptions}$ 來建立節點關係，然後最多再遍歷一次來找到根節點。
空間複雜度： $\mathcal{O}(n)$ 。

class Solution:
    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:
        mp = {} # val -> TreeNode
        pa = {} # child -> parent
        for u, v, is_left in descriptions:
            pa[v] = u
            if u not in mp:
                mp[u] = TreeNode(u)
            if v not in mp:
                mp[v] = TreeNode(v)
            if is_left:
                mp[u].left = mp[v]
            else:
                mp[u].right = mp[v]

        root = descriptions[0][0]
        while root in pa:
            root = pa[root]
        return mp[root]

class Solution {
public:
    TreeNode* createBinaryTree(vector<vector<int>>& descriptions) {
        unordered_map<int, TreeNode*> mp;
        unordered_map<int, int> pa;
        for (auto& desc : descriptions) {
            int u = desc[0], v = desc[1];
            bool is_left = desc[2];
            pa[v] = u;
            if (!mp.count(u)) mp[u] = new TreeNode(u);
            if (!mp.count(v)) mp[v] = new TreeNode(v);
            if (is_left) mp[u]->left = mp[v];
            else mp[u]->right = mp[v];
        }
        int root = descriptions[0][0];
        while (pa.count(root)) root = pa[root];
        return mp[root];
    }
};