2196. 根据描述创建二叉树 - 力扣（LeetCode）
2196. 根据描述创建二叉树 - 给你一个二维整数数组 descriptions ，其中 descriptions[i] = [parenti, childi, isLefti] 表示 parenti 是 childi 在 二叉树 中的 父节点，二叉树中各节点的值 互不相同 。此外： * 如果 isLefti == 1 ，那么 childi 就是 parenti 的左子节点。 * 如果 isLefti == 0 ，那么 childi 就是 parenti 的右子节点。 请你根据...
思路
比较常规的建树题，因为每个节点值各不相同，因此节点值可以当作每个节点的唯一标识。用哈希表维护节点值到树节点的映射，以及每个节点是否有前驱节点（没有前驱节点的节点就是根节点）。
代码
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;
}
};
1 个帖子 - 1 位参与者
来源: LinuxDo 最新话题查看原文