企业官网建设流程全解析

• 科学计算

导读

本文讲解力扣第 283 场周赛的2196. 根据描述创建二叉树（Create Binary Tree From Descriptions）题解。该题输入是一系列[parent, child, isLeft]三元组描述，要求还原整棵二叉树并返回根节点。全文围绕两条主线展开：一是用"整数值 → 节点指针"哈希表建树、再用哈希集合排除法定位根节点的基础解法；二是利用异或（XOR）自反性将根节点定位优化到不依赖任何集合，把空间复杂度从两个哈希结构降为一个哈希表。文中附 Python、Java、C++、Go、JavaScript、Rust 六种语言的完整实现，并给出当前仓库 codeforces-go 中对应的 Go 源码与测试用例，供读者验证与对照学习。

题目背景与仓库对应实现

该题在力扣的题号是 2196，属于第 283 场周赛第三题（Weekly Contest 283，Problem C）。本仓库codeforces-go将周赛题按场次归档，本题对应目录为 leetcode/weekly/283/c/，其中包含：

• c.go —— Go 语言题解源码，包含基础版createBinaryTree1和优化版createBinaryTree两个实现；
• c_test.go —— 由本仓库模板自动生成的测试文件；
• 2196.md —— 本题题解文档，即本文主体内容来源。

测试文件头部的注释// Code generated by copypasta/template/leetcode/generator_test.go表明，该测试是通过仓库的 leetcode 模板生成器 生成的，验证时只需go test ./leetcode/weekly/283/c/即可跑通两组样例。

题意：输入的是节点整数值，不是节点

题目输入descriptions的每一行是[parent, child, isLeft]这样的三元组：

• parent：父节点的整数值；
• child：子节点的整数值；
• isLeft：当值为1时表示child是parent的左孩子，为0时表示右孩子。

关键在于：输入给出的是节点的整数值，而不是现成的TreeNode节点对象。因此我们必须手动创建节点。例如有两条边50 → 20和20 → 15：

1. 先创建值为50、20的节点，把20挂到50的左孩子上；
2. 处理20 → 15时，由于20对应的节点之前已经创建过，我们需要知道"整数 20 对应哪个TreeNode节点"，所以需要一个从整数值映射到节点指针的哈希表nodes。

在 Go 语言中，TreeNode的定义与 LeetCode 官方一致，仓库中定义于 leetcode/testutil/predefined_type.go#L9-L13：

type TreeNode struct { Val int Left *TreeNode Right *TreeNode }

仓库的测试工具还在同一文件中提供了与 LeetCode 完全一致的树形序列化/反序列化逻辑：buildTreeNode负责把[1,2,null,null,3,4]这样的层序字符串解析成TreeNode（predefined_type.go#L16-L54），toRawString则负责把树反向序列化为层序字符串用于结果比对（predefined_type.go#L56-L85），这正是测试用例中[50,20,80,15,17,19]这类期望输出的解析基础。

基础解法：哈希表建树 + 哈希集合找根

思路

建树完成后，需要返回二叉树的根节点。问题转化为：怎么判断谁是二叉树的根？

用一个哈希集合children记录"哪些节点值有父节点"。由于题目保证输入能构成一棵有效的二叉树，那么遍历哈希表nodes，不在children中的节点值即为根节点。

六语言完整实现

Python3

class Solution: def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]: nodes = {} # val -> TreeNode children = set() # 建树 for x, y, is_left in descriptions: if x not in nodes: nodes[x] = TreeNode(x) if y not in nodes: nodes[y] = TreeNode(y) if is_left: nodes[x].left = nodes[y] else: nodes[x].right = nodes[y] children.add(y) # y 不是根节点 for x, node in nodes.items(): if x not in children: # node 是根节点 return node # 测试用例保证可以构造出有效的二叉树

Java

class Solution { public TreeNode createBinaryTree(int[][] descriptions) { int n = descriptions.length; Map<Integer, TreeNode> nodes = new HashMap<>(n + 1, 1); // 预分配空间 Set<Integer> children = new HashSet<>(n, 1); // 建树 for (int[] d : descriptions) { int x = d[0], y = d[1]; nodes.computeIfAbsent(x, _ -> new TreeNode(x)); nodes.computeIfAbsent(y, _ -> new TreeNode(y)); if (d[2] == 1) { nodes.get(x).left = nodes.get(y); } else { nodes.get(x).right = nodes.get(y); } children.add(y); // y 不是根节点 } for (Map.Entry<Integer, TreeNode> e : nodes.entrySet()) { if (!children.contains(e.getKey())) { // e.getValue() 是根节点 return e.getValue(); } } // 测试用例保证可以构造出有效的二叉树 throw new IllegalArgumentException("descriptions is not a valid binary tree"); } }

C++

class Solution { public: TreeNode* createBinaryTree(vector<vector<int>>& descriptions) { int n = descriptions.size(); unordered_map<int, TreeNode*> nodes; nodes.reserve(n + 1); // 预分配空间 unordered_set<int> children; children.reserve(n); // 预分配空间 // 建树 for (auto& d : descriptions) { int x = d[0], y = d[1]; if (!nodes.contains(x)) { nodes[x] = new TreeNode(x); } if (!nodes.contains(y)) { nodes[y] = new TreeNode(y); } if (d[2]) { nodes[x]->left = nodes[y]; } else { nodes[x]->right = nodes[y]; } children.insert(y); // y 不是根节点 } for (auto& [x, node] : nodes) { if (!children.contains(x)) { // node 是根节点 return node; } } // 测试用例保证可以构造出有效的二叉树 throw invalid_argument("descriptions is not a valid binary tree"); } };

Go（与仓库 c.go#L6-L36 中的createBinaryTree1完全一致）

func createBinaryTree1(descriptions [][]int) *TreeNode { n := len(descriptions) nodes := make(map[int]*TreeNode, n+1) // 预分配空间 children := make(map[int]bool, n) // 建树 for _, d := range descriptions { x, y := d[0], d[1] if nodes[x] == nil { nodes[x] = &TreeNode{Val: x} } if nodes[y] == nil { nodes[y] = &TreeNode{Val: y} } if d[2] == 1 { nodes[x].Left = nodes[y] } else { nodes[x].Right = nodes[y] } children[y] = true // y 不是根节点 } for x, node := range nodes { if !children[x] { // node 是根节点 return node } } // 测试用例保证可以构造出有效的二叉树 panic("不是有效的二叉树") }

JavaScript

var createBinaryTree = function(descriptions) { const nodes = new Map(); const children = new Set(); // 建树 for (const [x, y, isLeft] of descriptions) { if (!nodes.has(x)) { nodes.set(x, new TreeNode(x)); } if (!nodes.has(y)) { nodes.set(y, new TreeNode(y)); } if (isLeft) { nodes.get(x).left = nodes.get(y); } else { nodes.get(x).right = nodes.get(y); } children.add(y); // y 不是根节点 } for (const [x, node] of nodes) { if (!children.has(x)) { // node 是根节点 return node; } } // 测试用例保证可以构造出有效的二叉树 throw new Error("descriptions is not a valid binary tree"); };

Rust

use std::cell::RefCell; use std::collections::{HashMap, HashSet}; use std::rc::Rc; impl Solution { pub fn create_binary_tree(descriptions: Vec<Vec<i32>>) -> Option<Rc<RefCell<TreeNode>>> { let n = descriptions.len(); let mut nodes = HashMap::with_capacity(n + 1); // 预分配空间 let mut children = HashSet::with_capacity(n); // 建树 for d in descriptions { let x = d[0]; let y = d[1]; nodes.entry(x).or_insert_with(|| Rc::new(RefCell::new(TreeNode::new(x)))); nodes.entry(y).or_insert_with(|| Rc::new(RefCell::new(TreeNode::new(y)))); if d[2] == 1 { nodes.get(&x)?.borrow_mut().left = nodes.get(&y).cloned(); } else { nodes.get(&x)?.borrow_mut().right = nodes.get(&y).cloned(); } children.insert(y); // y 不是根节点 } for (x, node) in nodes { if !children.contains(&x) { // node 是根节点 return Some(node); } } // 测试用例保证可以构造出有效的二叉树 unreachable!() } }

小技巧：预分配空间

注意各语言在创建哈希表/集合时都做了容量预分配：Java 的new HashMap<>(n + 1, 1)、C++ 的nodes.reserve(n + 1)、Go 的make(map[int]*TreeNode, n+1)、Rust 的HashMap::with_capacity(n + 1)。原因是descriptions最多描述n + 1个不同节点（n条边对应一棵有n + 1个节点的树），提前分配可以避免扩容带来的额外哈希搬迁开销，是竞赛代码中的常见优化。

正确性要点

• children记录的是子节点y，因为凡是出现在child位置的节点必然有父节点、必然不是根；
• 根节点是树中唯一"从未作为子节点出现"的节点；
• 由于题目保证输入是有效的二叉树，遍历nodes时一定能找到唯一满足条件的节点；若输入的边有环或断开（形不成有效树），各语言实现分别以panic/throw兜底报错。

优化：用异或的性质直接算出根节点

核心思路

基础解法需要额外维护一个children集合来排除法定位根节点。优化解法的思路来自经典题136. 只出现一次的数字（题解）：

把树上每个值异或一遍，再把所有儿子child_i异或一遍。由于同一个值异或两次等于 0，所以最终异或和恰好等于根节点的值。

原理拆解：在二叉树中，每个非根节点恰好出现两次——一次作为它自身的节点值，一次作为某条边的child；而根节点只出现一次（它只作为自身节点值出现，永远不会出现在child位置）。对"所有节点值"和"所有 child 值"统一做异或：

• 非根节点：自身值 ^ 自己的 child 出现 = 出现两次 → 异或后抵消为 0；
• 根节点：只异或一次 → 保留下来。

因此异或和的最终结果就是根节点的整数值，最后用nodes[root]直接取回根节点指针即可，连遍历nodes找根都省了。

在代码上，可以进一步把两次异或合并进一次建树循环：x第一次出现时root ^= x，y第一次出现时root ^= y，同时每一行边都无条件root ^= y。这样"节点值出现一次"与"作为 child 出现一次"都在同一轮循环内完成异或抵消。

六语言完整实现

Python3

class Solution: def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]: nodes = {} # val -> TreeNode root = 0 for x, y, is_left in descriptions: if x not in nodes: nodes[x] = TreeNode(x) root ^= x if y not in nodes: nodes[y] = TreeNode(y) root ^= y if is_left: nodes[x].left = nodes[y] else: nodes[x].right = nodes[y] root ^= y return nodes[root]

Java

class Solution { public TreeNode createBinaryTree(int[][] descriptions) { Map<Integer, TreeNode> nodes = new HashMap<>(descriptions.length + 1, 1); // 预分配空间 int root = 0; for (int[] d : descriptions) { int x = d[0], y = d[1]; if (!nodes.containsKey(x)) { nodes.put(x, new TreeNode(x)); root ^= x; } if (!nodes.containsKey(y)) { nodes.put(y, new TreeNode(y)); root ^= y; } if (d[2] == 1) { nodes.get(x).left = nodes.get(y); } else { nodes.get(x).right = nodes.get(y); } root ^= y; } return nodes.get(root); } }

C++

class Solution { public: TreeNode* createBinaryTree(vector<vector<int>>& descriptions) { unordered_map<int, TreeNode*> nodes; nodes.reserve(descriptions.size() + 1); // 预分配空间 int root = 0; for (auto& d : descriptions) { int x = d[0], y = d[1]; if (!nodes.contains(x)) { nodes[x] = new TreeNode(x); root ^= x; } if (!nodes.contains(y)) { nodes[y] = new TreeNode(y); root ^= y; } if (d[2]) { nodes[x]->left = nodes[y]; } else { nodes[x]->right = nodes[y]; } root ^= y; } return nodes[root]; } };

Go（与仓库 c.go#L38-L61 中的createBinaryTree完全一致）

func createBinaryTree(descriptions [][]int) *TreeNode { nodes := make(map[int]*TreeNode, len(descriptions)+1) // 预分配空间 root := 0 for _, d := range descriptions { x, y := d[0], d[1] if nodes[x] == nil { nodes[x] = &TreeNode{Val: x} root ^= x } if nodes[y] == nil { nodes[y] = &TreeNode{Val: y} root ^= y } if d[2] == 1 { nodes[x].Left = nodes[y] } else { nodes[x].Right = nodes[y] } root ^= y } return nodes[root] }

JavaScript

var createBinaryTree = function(descriptions) { const nodes = new Map(); let root = 0; for (const [x, y, isLeft] of descriptions) { if (!nodes.has(x)) { nodes.set(x, new TreeNode(x)); root ^= x; } if (!nodes.has(y)) { nodes.set(y, new TreeNode(y)); root ^= y; } if (isLeft) { nodes.get(x).left = nodes.get(y); } else { nodes.get(x).right = nodes.get(y); } root ^= y; } return nodes.get(root); };

Rust

use std::cell::RefCell; use std::collections::HashMap; use std::rc::Rc; impl Solution { pub fn create_binary_tree(descriptions: Vec<Vec<i32>>) -> Option<Rc<RefCell<TreeNode>>> { let mut nodes = HashMap::with_capacity(descriptions.len() + 1); // 预分配空间 let mut root = 0; for d in descriptions { let x = d[0]; let y = d[1]; nodes.entry(x).or_insert_with(|| { root ^= x; Rc::new(RefCell::new(TreeNode::new(x))) }); nodes.entry(y).or_insert_with(|| { root ^= y; Rc::new(RefCell::new(TreeNode::new(y))) }); if d[2] == 1 { nodes.get(&x)?.borrow_mut().left = nodes.get(&y).cloned(); } else { nodes.get(&x)?.borrow_mut().right = nodes.get(&y).cloned(); } root ^= y; } nodes.remove(&root) } }

注意 Rust 版本里entry(...).or_insert_with(...)的闭包中同时执行了root ^= x，这是利用"只有首次插入时才异或该值"的语义，与其它语言中if x not in nodes的分支判断等价。结尾用nodes.remove(&root)从哈希表中取出根节点并释放所有权，符合 Rust 的所有权模型。

为什么root ^= x只在首次出现时执行

• root ^= x（首次出现时）：节点x作为"节点值"贡献一次异或；
• 每行边无条件root ^= y：节点y作为"子节点"贡献一次异或；
• 非根节点既作为节点值、又作为某条边的 child 出现，两次异或相互抵消；
• 根节点只作为节点值出现一次，异或和最终就是根节点的值。

这个技巧本质上就是位运算中"异或的归零律"（a ^ a = 0）的应用，与只出现一次的数字是同一思想，属于可以迁移复用的套路。

复杂度分析

两种解法的时间复杂度与空间复杂度相同：

• 时间复杂度：O(n)，其中 n 是descriptions的长度。建树阶段每条边处理一次，每次哈希操作均摊 O(1)；基础解法最后遍历nodes找根也只需 O(n)。
• 空间复杂度：O(n)。nodes哈希表需要存下全部 n+1 个节点；基础解法额外需要一个children集合（O(n)），优化解法则完全省去了该集合。

因此，优化版本在时间复杂度不变的前提下，把空间占用从"两个 O(n) 结构"降为"一个 O(n) 结构"，代码也更短，不需要再单独写一段找根的逻辑。

仓库测试验证

本题的 Go 实现由仓库的测试工具testutil.RunLeetCodeFuncWithExamples驱动验证（c_test.go），测试用例与 LeetCode 官方一致：

输入：[[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]] 输出：[50,20,80,15,17,19] 输入：[[1,2,1],[2,3,0],[3,4,1]] 输出：[1,2,null,null,3,4]

测试框架通过反射解析输入输出，并把输出统一序列化为层序字符串后与期望值比对（leetcode.go#L237-L326）；同时在跑全部用例时还会自动进行超时检测（isTLE），可以当作在线评测环境的本地复刻。测试文件已标注题目来源 leetcode-cn.com weekly-contest-283。

本地运行验证方式：

go test ./leetcode/weekly/283/c/

targetCaseNum := -1表示运行全部测试用例（负数表示从最后一个用例开始向前偏移，详见 leetcode.go#L250-L253），两个用例均通过即说明两种实现正确。

总结

2196. 根据描述创建二叉树的核心考点有两个：

1. 用哈希表管理"整数值 → 节点指针"的映射：解决输入给的是值而非对象、建树时需要反复定位既有节点的问题；
2. 确定根节点：基础版用children哈希集合排除所有非根节点；优化版利用异或自反性，把"所有节点值 ^ 所有 child 值"的异或和直接算成根节点值，省去一个集合并简化代码。

若想继续练习同主题题目，可在树题单的「§2.10 创建二叉树」小节找到更多变式；位运算方向的补充训练可参考位运算专题，本仓库 copypasta/bits.go 也整理了大量异或、按位操作的模板与题目线索可供查阅。

• 科学计算