从描述列表构建二叉树（LeetCode 2196）：哈希建树与异或定位根节点

科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载导读本文讲解力扣第 283 场周赛的2196. 根据描述创建二叉树Create Binary Tree From Descriptions题解。该题输入是一系列[parent, child, isLeft]三元组描述要求还原整棵二叉树并返回根节点。全文围绕两条主线展开一是用整数值 → 节点指针哈希表建树、再用哈希集合排除法定位根节点的基础解法二是利用异或XOR自反性将根节点定位优化到不依赖任何集合把空间复杂度从两个哈希结构降为一个哈希表。文中附 Python、Java、C、Go、JavaScript、Rust 六种语言的完整实现并给出当前仓库 codeforces-go 中对应的 Go 源码与测试用例供读者验证与对照学习。题目背景与仓库对应实现该题在力扣的题号是 2196属于第 283 场周赛第三题Weekly Contest 283Problem 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先创建值为50、20的节点把20挂到50的左孩子上处理20 → 15时由于20对应的节点之前已经创建过我们需要知道整数 20 对应哪个TreeNode节点所以需要一个从整数值映射到节点指针的哈希表nodes。在 Go 语言中TreeNode的定义与 LeetCode 官方一致仓库中定义于 leetcode/testutil/predefined_type.go#L9-L13type TreeNode struct { Val int Left *TreeNode Right *TreeNode }仓库的测试工具还在同一文件中提供了与 LeetCode 完全一致的树形序列化/反序列化逻辑buildTreeNode负责把[1,2,null,null,3,4]这样的层序字符串解析成TreeNodepredefined_type.go#L16-L54toRawString则负责把树反向序列化为层序字符串用于结果比对predefined_type.go#L56-L85这正是测试用例中[50,20,80,15,17,19]这类期望输出的解析基础。基础解法哈希表建树 哈希集合找根思路建树完成后需要返回二叉树的根节点。问题转化为怎么判断谁是二叉树的根用一个哈希集合children记录哪些节点值有父节点。由于题目保证输入能构成一棵有效的二叉树那么遍历哈希表nodes不在children中的节点值即为根节点。六语言完整实现Python3class 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 # 测试用例保证可以构造出有效的二叉树Javaclass Solution { public TreeNode createBinaryTree(int[][] descriptions) { int n descriptions.length; MapInteger, TreeNode nodes new HashMap(n 1, 1); // 预分配空间 SetInteger 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.EntryInteger, TreeNode e : nodes.entrySet()) { if (!children.contains(e.getKey())) { // e.getValue() 是根节点 return e.getValue(); } } // 测试用例保证可以构造出有效的二叉树 throw new IllegalArgumentException(descriptions is not a valid binary tree); } }Cclass Solution { public: TreeNode* createBinaryTree(vectorvectorint descriptions) { int n descriptions.size(); unordered_mapint, TreeNode* nodes; nodes.reserve(n 1); // 预分配空间 unordered_setint 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, n1) // 预分配空间 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(不是有效的二叉树) }JavaScriptvar 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); };Rustuse std::cell::RefCell; use std::collections::{HashMap, HashSet}; use std::rc::Rc; impl Solution { pub fn create_binary_tree(descriptions: VecVeci32) - OptionRcRefCellTreeNode { 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, n1)、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 ^ xy第一次出现时root ^ y同时每一行边都无条件root ^ y。这样节点值出现一次与作为 child 出现一次都在同一轮循环内完成异或抵消。六语言完整实现Python3class 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]Javaclass Solution { public TreeNode createBinaryTree(int[][] descriptions) { MapInteger, 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); } }Cclass Solution { public: TreeNode* createBinaryTree(vectorvectorint descriptions) { unordered_mapint, 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] }JavaScriptvar 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); };Rustuse std::cell::RefCell; use std::collections::HashMap; use std::rc::Rc; impl Solution { pub fn create_binary_tree(descriptions: VecVeci32) - OptionRcRefCellTreeNode { 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哈希表需要存下全部 n1 个节点基础解法额外需要一个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. 根据描述创建二叉树的核心考点有两个用哈希表管理整数值 → 节点指针的映射解决输入给的是值而非对象、建树时需要反复定位既有节点的问题确定根节点基础版用children哈希集合排除所有非根节点优化版利用异或自反性把所有节点值 ^ 所有 child 值的异或和直接算成根节点值省去一个集合并简化代码。若想继续练习同主题题目可在树题单的「§2.10 创建二叉树」小节找到更多变式位运算方向的补充训练可参考位运算专题本仓库 copypasta/bits.go 也整理了大量异或、按位操作的模板与题目线索可供查阅。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐LeetCode 1104 二叉树寻路用满二叉树的“定值求和”规则从之字形标签逆推回根节点LeetCode 1104 二叉树寻路用满二叉树的“定值求和”规则从之字形标签逆推回根节点 本篇技术指南基于仓库中的题解文档 1104.path in zi文档教程知识库从前序与中序遍历序列构造二叉树LeetCode 105递归分治与哈希表索引推导详解从前序与中序遍历序列构造二叉树LeetCode 105递归分治与哈希表索引推导详解 导读 本文以《Krahets 笔面试精选 88 题》中 105. 从前示例工程AlgoNote 题解精讲从前序与中序遍历序列构造二叉树LeetCode 0105 · 递归分治 哈希表优化AlgoNote 题解精讲从前序与中序遍历序列构造二叉树LeetCode 0105 · 递归分治 哈希表优化 本篇为「算法通关手册」AlgoNote教程文档知识库上一篇微信单向好友检测工具5分钟快速清理无效社交关系下一篇3个技巧解决网盘下载痛点智能直链提取实战方案创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考