根据描述创建二叉树

题目

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

此外：

如果 isLefti == 1 ，那么 childi 就是 parenti 的左子节点。

如果 isLefti == 0 ，那么 childi 就是 parenti 的右子节点。

请你根据 descriptions 的描述来构造二叉树并返回其 根节点 。

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/create-binary-tree-from-descriptions

思路

构建邻接表unordered_map、使用深搜、广搜
使用哈希表unordered_map

代码

方法一

/**
 * 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>、使用深搜、广搜
        // 使用哈希表unordered_map

        unordered_set<int> st;
        int root;

        for(auto ele:descriptions){
            st.insert(ele[1]);
        }

        for(auto ele:descriptions){

            if(!st.count(ele[0])){
            root=ele[0];              // 找到根
            break;
            }
        }

        unordered_map<int,vector<int>> mp;

        for(auto ele:descriptions){         // 使用邻接表

            mp[ele[0]].resize(2,0);
            mp[ele[0]][ele[2]]=ele[1];
        }


        queue<TreeNode*> q;
        TreeNode* temp=new TreeNode(root,nullptr,nullptr);
        q.push(temp);
        TreeNode* r=temp;



        while(!q.empty()){

            temp=q.front();
            q.pop();

            if(mp[temp->val].size()&&mp[temp->val][0]){
                temp->right=new TreeNode(mp[temp->val][0],nullptr,nullptr);
                q.push(temp->right);
            }

            if(mp[temp->val].size()&&mp[temp->val][1]){
                temp->left=new TreeNode(mp[temp->val][1],nullptr,nullptr);
                q.push(temp->left);
            }
        }

        return r;
        
    }

    TreeNode* preorder_traverse(int val,unordered_map<int,vector<int>> mp){


        TreeNode* temp=new TreeNode(val,nullptr,nullptr);

        if(mp[temp->val].size()&&mp[temp->val][1])
        temp->left=preorder_traverse(mp[temp->val][1],mp);
        if(mp[temp->val].size()&&mp[temp->val][0])
        temp->right=preorder_traverse(mp[temp->val][0],mp);

        return temp;
    }
};

方法二

class Solution {
public:
    TreeNode* createBinaryTree(vector<vector<int>>& descriptions) {
        unordered_map<int, bool> isRoot;   // 数值对应的节点是否为根节点的哈希表
        unordered_map<int, TreeNode*> nodes;   // 数值与对应节点的哈希表
        for (const auto& d: descriptions) {
            int p = d[0];
            int c = d[1];
            bool left = d[2];
            if (!isRoot.count(p)) {
                isRoot[p] = true;
            }
            isRoot[c] = false;
            // 创建或更新节点
            if (!nodes.count(p)) {
                nodes[p] = new TreeNode(p);
            }
            if (!nodes.count(c)) {
                nodes[c] = new TreeNode(c);
            }
            if (left) {
                nodes[p]->left = nodes[c];
            } else {
                nodes[p]->right = nodes[c];
            }
        }
        // 寻找根节点
        int root = -1;
        for (const auto& [val, r]: isRoot) {
            if (r) {
                root = val;
                break;
            }
        }
        return nodes[root];
    }
};