2. Linux.do
  3. Leetcode每日一题 —— 2196. 根据描述创建二叉树

Leetcode每日一题 —— 2196. 根据描述创建二叉树

SomeBottle 2026-06-07 09:46 1



思路


比较常规的建树题，因为每个节点值各不相同，因此节点值可以当作每个节点的唯一标识。用哈希表维护节点值到树节点的映射，以及每个节点是否有前驱节点（没有前驱节点的节点就是根节点）。



代码


class Solution {

public:

    TreeNode* createBinaryTree(vector<vector<int>>& descriptions) {

        // 最后没有父节点的节点就是根节点

        unordered_map<int, TreeNode*> tMap;  // 哈希表存节点值到节点的映射

        unordered_map<TreeNode*, bool> pMap; // 记录每个节点有没有前驱

        for (auto& d : descriptions) {

            if (tMap.count(d[0]) == 0) {

                // 如果还没有这个父节点就创建

                tMap[d[0]] = new TreeNode(d[0]);

                pMap[tMap[d[0]]] = false;

            }

            // 如果没有这个孩子节点也要创建

            if (tMap.count(d[1]) == 0) {

                tMap[d[1]] = new TreeNode(d[1]);

            }

            if (d[2] == 1) {

                tMap[d[0]]->left = tMap[d[1]];

            } else {

                tMap[d[0]]->right = tMap[d[1]];

            }

            pMap[tMap[d[1]]] = true;

        }

        // 扫描找到根节点

        for (auto it = pMap.begin(); it != pMap.end(); it++) {

            if (!it->second) {

                return it->first;

            }

        }

        return nullptr;

    }

};
最新回复 (3)
  • CPython 06-07 10:31
    1楼 
    # 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]:
    
        vis = set()
    
        nodes = {}
    
        for p, c, b in descriptions:
    
            if p not in nodes:
    
                nodes[p] = TreeNode(p)
    
            if c not in nodes:
    
                nodes[c] = TreeNode(c)
    
            if b:
    
                nodes[p].left = nodes[c]
    
            else:
    
                nodes[p].right = nodes[c]
    
            vis.add(c)
    
        for p, c, b in descriptions:
    
            if p not in vis:
    
                return nodes[p]
  • Lvvvv 06-07 11:32
    2楼

    感觉是有点丑陋写的


    /**
    
 * 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) {
    
        TreeNode *ppar = nullptr, *pson = nullptr;
    
        unordered_map<int,TreeNode*> s;
    
        unordered_map<int,int> d;
    
        auto getp = [&s](int id) -> TreeNode* {
    
            if(s.find(id) == s.end()) {
    
                s[id] = new TreeNode(id);
    
            }
    
            return s[id];
    
        };
    
        for(const auto& v: descriptions) {
    
            int par = v[0],son = v[1],isleft = v[2];
    
            ppar = getp(par);
    
            pson = getp(son);
    
            if(d.find(par) == d.end()) {
    
                d[par] = 0;
    
            }
    
            d[son] = 1;
    
            if(isleft) ppar->left = pson;
    
            else ppar->right = pson;
    
        }
    
        for(auto [k,v] : d) {
    
            if(v == 0) {
    
                return s[k];
    
            }
    
        }
    
        return nullptr;
    
    }
    
};
  • 咪帕 06-07 11:50
    3楼 
    /**
    
 * 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*> m;
    
        unordered_set<int> set;
    
        for (auto& e : descriptions) {
    
            if (!set.contains(e[1])) {
    
                set.insert(e[1]);
    
            }
    
            auto parent = m.contains(e[0]) ? m[e[0]] : new TreeNode(e[0]);
    
            auto child = m.contains(e[1]) ? m[e[1]] : new TreeNode(e[1]);
    
            if (e[2]) {
    
                parent->left = child;
    
            } else {
    
                parent->right = child;
    
            }
    
            m[e[0]] = parent;
    
            m[e[1]] = child;
    
        } 
    
        for (auto [k, v] : m) {
    
            if (!set.contains(k)) {
    
                return v;
    
            }
    
        }
    
        return nullptr;
    
    }
    
};
* 帖子来源Linux.do
附近帖子
返回
飞读
随机推荐