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

这道题到底在问什么

输入

descriptions=[[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]]

输出

根=50 · 层序 [50,20,80,15,17,19]

输入

descriptions=[[1,2,1],[2,3,0],[3,4,1]]

输出

根=1 · [1,2,null,null,3,4]

最优解：一步一步想明白

1. 3记牢这两句:哈希表保证同名同节点、乱序也能接对边;孩子集合专门用来挑根。下面从第一条描述开始,一条一条走。
2. 4哈希表 = 空舞台先用淡色把这六个值将来所在的位置摆出来,当作最终形态的参照。此刻哈希表还是空的,一个节点都没真正建。约定颜色:淡色表示还没建,蓝色表示已经进了哈希表,绿色表示这个值当过别人的孩子。下面每读一条描述,该新建的值就会亮起来。
3. 5new/取 20 与 15读第一条描述 [20,15,1]。parent 20 和 child 15 都第一次出现,各新建一个节点。现在紫色是父亲 20,橙色是孩子 15。
4. 620.left = 15isLeft 是 1,把 15 接到 20 的左孩子指针上。看 20 到 15 这条边,归属就定下来了。
5. 7孩子集合 += 1515 现在是别人的孩子了,把它记进孩子集合,同时它变成绿色。凡是进了这个集合的值,都不可能是根。目前孩子集合里有 15。
6. 8new/取 20 与 17读第二条描述 [20,17,0]。parent 20 已在哈希表里,取出复用;child 17 是新的,新建。现在紫色是父亲 20,橙色是孩子 17。
7. 920.right = 17isLeft 是 0,把 17 接到 20 的右孩子指针上。看 20 到 17 这条边,归属就定下来了。
8. 10孩子集合 += 1717 现在是别人的孩子了,把它记进孩子集合,同时它变成绿色。凡是进了这个集合的值,都不可能是根。目前孩子集合里有 15, 17。
9. 11new/取 50 与 20读第三条描述 [50,20,1]。parent 50 是新的,新建;child 20 已在哈希表里,取出复用。现在紫色是父亲 50,橙色是孩子 20。
10. 1250.left = 20isLeft 是 1,把 20 接到 50 的左孩子指针上。看 50 到 20 这条边,归属就定下来了。这一步很关键:20 顶着 15、17 那半棵小树,整个被挂到了主干 50 底下。
11. 13孩子集合 += 2020 现在是别人的孩子了,把它记进孩子集合,同时它变成绿色。凡是进了这个集合的值,都不可能是根。目前孩子集合里有 20, 15, 17。
12. 14new/取 50 与 80读第四条描述 [50,80,0]。parent 50 已在哈希表里,取出复用;child 80 是新的,新建。现在紫色是父亲 50,橙色是孩子 80。
13. 1550.right = 80isLeft 是 0,把 80 接到 50 的右孩子指针上。看 50 到 80 这条边,归属就定下来了。
14. 16孩子集合 += 8080 现在是别人的孩子了,把它记进孩子集合,同时它变成绿色。凡是进了这个集合的值,都不可能是根。目前孩子集合里有 20, 80, 15, 17。
15. 17new/取 80 与 19读最后一条描述 [80,19,1]。parent 80 已在哈希表里,取出复用;child 19 是新的,新建。注意 80 之前作为别人的孩子已经登记过绿色了,这次它换个身份当父亲。现在紫色是父亲 80,橙色是孩子 19。
16. 1880.left = 19isLeft 是 1,把 19 接到 80 的左孩子指针上。看 80 到 19 这条边,归属就定下来了。到这里,整棵树的边就全接完了。
17. 19孩子集合 += 1919 现在是别人的孩子了,把它记进孩子集合,同时它变成绿色。凡是进了这个集合的值,都不可能是根。目前孩子集合里有 20, 80, 15, 17, 19。
18. 20待找: 不在孩子集合的值五条描述读完,边全接好了。可根是谁?规律只有一条:根是唯一一个从来没当过别人孩子的值。现在孩子集合里是 20, 80, 15, 17, 19,绿色的这五个都当过孩子。只剩蓝色的 50 还没进过集合,拿几个值一个个去对照确认一下。
19. 2120 ∈ 孩子集合20 在孩子集合里,它当过别人的孩子,不是根,跳过看下一个。
20. 2215 ∈ 孩子集合15 在孩子集合里,它当过别人的孩子,不是根,跳过看下一个。
21. 2317 ∈ 孩子集合17 在孩子集合里,它当过别人的孩子,不是根,跳过看下一个。
22. 2450 ∉ 孩子集合轮到 50,它不在孩子集合里。也就是说,没有任何一条描述把 50 当成过孩子,它就是这棵树的根节点。
23. 25根 = 50 · 层序 50,20,80,15,17,19找到根 50,从它出发,这棵树就是答案,层序遍历正好是 50,20,80,15,17,19。回头看整道题其实就两步:用哈希表按值建节点、取节点、接边,保证乱序也接得对;再用孩子集合挑出那个没当过孩子的根。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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]

#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;
    }
};

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;
    }
}

复杂度

面试官可能追问