根据描述创建二叉树 图解题解

一堆父子描述，怎么拼回原来那棵树

给一个二维数组 descriptions，每条是 [parent, child, isLeft]：isLeft 是 1 表示 child 是 parent 的左孩子，0 是右孩子。各节点值互不相同，让你拼出二叉树、返回根节点。题面例子 descriptions=[[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]]，根是 50，层序遍历是 50,20,80,15,17,19。

读一条就新建一个节点，两处会崩

描述是乱序的，没法从根往下顺着建。第一反应是读一条就把两个值各造节点、按 isLeft 接边，但两处会崩：同一个值会反复出现，20 既在 [20,15,1] 当父亲、又在 [50,20,1] 当孩子，重复造新节点会让父子指向不同实例，那半棵就断开；根也不能拿第一条的 parent 当，它其实可能是别人的孩子。

同值只留一个节点，根是没人认领的那个

先解决同值：用哈希表按值存节点，也就是给每个值配一张能直接查到它节点的表。每读到一个值先查表，有就取旧节点复用，没有才新建，同一个值全程只有一个实例。

再解决找根：另开一个 children 集合，凡当过 child 的值都塞进去。所有值里唯一没进这个集合的就是根，它从没被任何描述当成孩子。

一趟扫描接边，末尾用差集挑根

代码就一趟遍历：每条 [parent, child, isLeft]，parent、child 缺谁补建谁，child 记进 children 集合，按 isLeft 让 parent 左或右指针指向 child 节点。扫完拿所有值的集合减去 children，剩下唯一那个值对应的节点就是根。

五条描述走一遍，50 怎么浮出来

拿题面五条逐条过。[20,15,1]：20、15 都新建，20 左指向 15。[20,17,0]：20 复用，17 新建，20 右指向 17。[50,20,1]：50 新建，20 复用，50 左指向 20，20 连着 15、17 挂到 50 底下。[50,80,0]：50 复用，80 新建，50 右指向 80。[80,19,1]：80 复用，19 新建，80 左指向 19。

五条读完，当过孩子的是 {15,17,20,80,19}，出现过的值 {15,17,20,50,80,19} 减掉它只剩 50。50 就是根，从它层序遍历，输出就是 50,20,80,15,17,19。

复用一松手，半棵树就断开

复杂度：设描述 n 条，每条只做常数次哈希操作，建取节点、接边、加值；最后找根遍历所有值。时间 O(n)，哈希表和 children 集合都不超过 2n 量级，空间 O(n)。

几个地方一松手就错。同值第二次出现必须取旧节点，重建一个会让父子指向不同实例，那半棵树当场断开。判根别认第一条的 parent，乱序里它常是别人的孩子。一个值还能既当父又当子：20 是 15、17 的父亲、又是 50 的孩子，照样进集合、照样不是根。单条描述时 parent 就是根。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
# 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]:
        nodes = defaultdict(TreeNode)
        children = set()
        for parent, child, isLeft in descriptions:
            if parent not in nodes:
                nodes[parent] = TreeNode(parent)
            if child not in nodes:
                nodes[child] = TreeNode(child)
            children.add(child)
            if isLeft:
                nodes[parent].left = nodes[child]
            else:
                nodes[parent].right = nodes[child]
        root = (set(nodes.keys()) - children).pop()
        return nodes[root]

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
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) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
/**
 * 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) {
        unordered_map<int, TreeNode*> nodes;
        unordered_set<int> children;
        for (const auto& d : descriptions) {
            int parent = d[0], child = d[1], isLeft = d[2];
            if (nodes.find(parent) == nodes.end()) {
                nodes[parent] = new TreeNode(parent);
            }
            if (nodes.find(child) == nodes.end()) {
                nodes[child] = new TreeNode(child);
            }
            if (isLeft) {
                nodes[parent]->left = nodes[child];
            } else {
                nodes[parent]->right = nodes[child];
            }
            children.insert(child);
        }
        for (const auto& [k, v] : nodes) {
            if (children.find(k) == children.end()) {
                return v;
            }
        }
        return nullptr;
    }
};

Java

import java.util.*;
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public TreeNode createBinaryTree(int[][] descriptions) {
        Map<Integer, TreeNode> nodes = new HashMap<>();
        Set<Integer> children = new HashSet<>();
        for (int[] d : descriptions) {
            int parent = d[0], child = d[1], isLeft = d[2];
            if (!nodes.containsKey(parent)) {
                nodes.put(parent, new TreeNode(parent));
            }
            if (!nodes.containsKey(child)) {
                nodes.put(child, new TreeNode(child));
            }
            if (isLeft == 1) {
                nodes.get(parent).left = nodes.get(child);
            } else {
                nodes.get(parent).right = nodes.get(child);
            }
            children.add(child);
        }
        for (Map.Entry<Integer, TreeNode> e : nodes.entrySet()) {
            if (!children.contains(e.getKey())) {
                return e.getValue();
            }
        }
        return null;
    }
}