日期：2026年6月7日
LeetCode 題目連結：2196. Create Binary Tree From Descriptions
解題想法
中級難度的題目。要用鏈結串列建二元樹。我先將每個節點的父節點、左子樹、右子樹分別存入字典之中，另外用一個集合儲存所有的節點。再找根節點，也就是所有節點當中唯一一個沒有父節點的節點。最後再用 BFS 或遞迴建樹。以下的程式碼速度不快，還可以再改進。
Python 程式碼
用 list 儲存待走訪的節點。Runtime: 202 ms, beats 15.04%. Memory: 28.30 MB, beats 24.19%.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:
# 儲存所有的節點值，記錄每個節點的父節點、左子節點、右子節點
parent = dict()
left_child = dict()
right_child = dict()
all_nodes = set()
for p, c, lr in descriptions:
all_nodes.add(p)
all_nodes.add(c)
parent[c] = p
if lr == 1:
left_child[p] = c
else:
right_child[p] = c
# 找出根節點的值
root_val = -1
for node in all_nodes:
if node not in parent:
root_val = node
break
# 用 list 建樹
root = TreeNode(val=root_val)
que = [root]
head = 0
while head < len(que):
curr = que[head]
head += 1
if curr.val in left_child:
curr.left = TreeNode(val = left_child[curr.val])
que.append(curr.left)
if curr.val in right_child:
curr.right = TreeNode(val = right_child[curr.val])
que.append(curr.right)
return root
用 deque 儲存待走訪的節點。Runtime: 206 ms, beats 13.82%. Memory: 28.14 MB, beats 25.41%.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
from collections import deque
class Solution:
def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:
parent = dict()
left_child = dict()
right_child = dict()
all_nodes = set()
for p, c, lr in descriptions:
all_nodes.add(p)
all_nodes.add(c)
parent[c] = p
if lr == 1:
left_child[p] = c
else:
right_child[p] = c
root_val = -1
for node in all_nodes:
if node not in parent:
root_val = node
break
root = TreeNode(val=root_val)
que = deque([root])
while que:
curr = que.popleft()
if curr.val in left_child:
curr.left = TreeNode(val = left_child[curr.val])
que.append(curr.left)
if curr.val in right_child:
curr.right = TreeNode(val = right_child[curr.val])
que.append(curr.right)
return root
遞迴。Runtime: 206 ms, beats 13.82%. Memory: 38.39 MB, beats 8.94%.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:
parent = dict()
left_child = dict()
right_child = dict()
all_nodes = set()
for p, c, lr in descriptions:
all_nodes.add(p)
all_nodes.add(c)
parent[c] = p
if lr == 1:
left_child[p] = c
else:
right_child[p] = c
root_val = -1
for node in all_nodes:
if node not in parent:
root_val = node
break
root = TreeNode(val=root_val)
def build(curr):
if curr.val in left_child:
curr.left = TreeNode(val = left_child[curr.val])
build(curr.left)
if curr.val in right_child:
curr.right = TreeNode(val = right_child[curr.val])
build(curr.right)
build(root)
return root
C++ 程式碼
用 vector 儲存待走訪的節點。Runtime: 586 ms, beats 5.26%. Memory: 326.48 MB, beats 5.12%.
/**
* 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:
TreeNode* createBinaryTree(vector<vector<int>>& descriptions) {
/* 儲存所有的節點值，記錄每個節點的父節點、左子節點、右子節點 */
map<int, int> parent, left_child, right_child;
set<int> all_nodes;
for(auto it : descriptions) {
int p = it[0], c = it[1], lr = it[2];
all_nodes.insert(p);
all_nodes.insert(c);
parent[c] = p;
if (lr == 1) {
left_child[p] = c;
} else {
right_child[p] = c;
}
}
/* 找出根節點的值 */
int root_val = -1;
for(int node : all_nodes) {
if (parent.count(node) == 0) {
root_val = node;
break;
}
}
/* 用 vector 建樹 */
TreeNode* root = new TreeNode(root_val);
vector<TreeNode*> que;
que.push_back(root);
size_t head = 0;
while(head < que.size()) {
auto curr = que[head];
head++;
if (left_child.count(curr->val) == 1) {
curr->left = new TreeNode(left_child[curr->val]);
que.push_back(curr->left);
}
if (right_child.count(curr->val) == 1) {
curr->right = new TreeNode(right_child[curr->val]);
que.push_back(curr->right);
}
}
return root;
}
};
用 queue 儲存待走訪的節點。Runtime: 568 ms, beats 5.26%. Memory: 321.90 MB, beats 5.12%.
/**
* 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:
TreeNode* createBinaryTree(vector<vector<int>>& descriptions) {
/* 儲存所有的節點值，記錄每個節點的父節點、左子節點、右子節點 */
map<int, int> parent, left_child, right_child;
set<int> all_nodes;
for(auto it : descriptions) {
int p = it[0], c = it[1], lr = it[2];
all_nodes.insert(p);
all_nodes.insert(c);
parent[c] = p;
if (lr == 1) {
left_child[p] = c;
} else {
right_child[p] = c;
}
}
/* 找出根節點的值 */
int root_val = -1;
for(int node : all_nodes) {
if (parent.count(node) == 0) {
root_val = node;
break;
}
}
/* 用 queue 建樹 */
TreeNode* root = new TreeNode(root_val);
queue<TreeNode*> que;
que.push(root);
while(!que.empty()) {
auto curr = que.front();
que.pop();
if (left_child.count(curr->val) == 1) {
curr->left = new TreeNode(left_child[curr->val]);
que.push(curr->left);
}
if (right_child.count(curr->val) == 1) {
curr->right = new TreeNode(right_child[curr->val]);
que.push(curr->right);
}
}
return root;
}
};
沒有留言:
張貼留言