2196.根据描述创建二叉树

发表于： 分类于：
字数： 1277 阅读：≈ 3分钟

🌳2196.根据描述创建二叉树

给你一个二维整数数组 descriptions ，其中 descriptions[i] = [parenti, childi, isLefti] 表示 parenti 是 childi 在 二叉树 中的 父节点，二叉树中各节点的值 互不相同 。此外：

如果 isLefti == 1 ，那么 childi 就是 parenti 的左子节点。 如果 isLefti == 0 ，那么 childi 就是 parenti 的右子节点。 请你根据 descriptions 的描述来构造二叉树并返回其 根节点 。

测试用例会保证可以构造出 有效 的二叉树。

示例

示例 1：

img

输入：descriptions = [[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]] 输出：[50,20,80,15,17,19] 解释：根节点是值为 50 的节点，因为它没有父节点。 结果二叉树如上图所示。

示例 2：

img

输入：descriptions = [[1,2,1],[2,3,0],[3,4,1]] 输出：[1,2,null,null,3,4] 解释：根节点是值为 1 的节点，因为它没有父节点。 结果二叉树如上图所示。

思路

基本思想

每一个描述都会创建一个新子树，包含一个根节点和一个孩子节点，重点就是如何讲子树连接起来

建立一个哈希表，建立子树时如果哈希表中已经有了节点，那么这个节点肯定要被连接到子树中，如果还没有此节点，就创建此节点，这样就可以将所有的子树一一连接在一起

并且一旦某个节点被连接到其他的子树中，入度就需要加一，最终统计入度为零的节点就是根节点

执行流程

遍历描述数组，创建子树，在创建子树时如果父节点和孩子节点不存在就创建

如果存在的话就直接判断孩子节点是否已经被创建，如果已经被创建，那就意味着两个子树之间需要进行链接，并且被连接的节点入度需要增加

遍历完描述数组之后，所有的子树被链接成了一颗完整的子树，最后的工作就是找到根节点并返回，此时入度数组就排上用场了，只需要找到入度为0的节点就是根节点

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution {
public:
    TreeNode* createBinaryTree(vector<vector<int>>& descriptions) {
        map<int,TreeNode*> tree;
        map<int,int>degreeIn;
        for(auto d:descriptions){//遍历描述数组创建子树
            int root=d[0];//父节点的值
            int child=d[1];//孩子节点的值
            int is_left=d[2];//是否是左孩子
            //没找到count就是0，取反之后变成1，从而会创建新的节点
            if(!tree.count(root)){//没找到根节点就创建
                tree[root]=new TreeNode(root);
            }
            if(!tree.count(child)){//没找到孩子节点就创建
                tree[child]=new TreeNode(child);
            }
            //在tree中搜索孩子节点将其连接上
            if(is_left){//如果是左孩子
                tree[root]->left=tree[child];
            }else{//如果是右孩子
                tree[root]->right=tree[child];
            }
            //孩子节点的入度加一
            degreeIn[child]++;
        }
        //寻找入度为0的根节点
        for(auto node:tree){
            int val=node.second->val;//按照节点的val去找
            if(!degreeIn[val]){//找到入度为0的节点就是根节点
                return node.second;//对组的遍历方式
            }
        }
        return nullptr;//没找到入度为0的根节点
    }
};

总结

主要有以下几个主要注意的点：

  1. 对于每一个单独的描述，创建一个子树很简单，难得是如何将单独的子树连接起来，因为描述没有按照遍历顺序给出
  2. 使用map标记节点是否被创建，这样创建新的子树是，如果孩子节点已经存在，那么可以直接连接，从而将两个子树连接到一起形成更大的子树
  3. 连接之后孩子节点的入度需要增加，为了最后搜索根节点

主要是考察代码能力，知道对组的遍历方式