列表

详情

2196. 根据描述创建二叉树

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

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

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

 

示例 1：

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

示例 2：

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

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
/** * 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) { } };

python3 解法, 执行用时: 552 ms, 内存消耗: 22.6 MB, 提交时间: 2022-11-19 18:22:55 

# 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]:
        isRoot = {}   # 数值对应的节点是否为根节点的哈希表
        nodes = {}   # 数值与对应节点的哈希表
        for p, c, left in descriptions:
            if p not in isRoot:
                isRoot[p] = True
            isRoot[c] = False
            # 创建或更新节点
            if p not in nodes:
                nodes[p] = TreeNode(p)
            if c not in nodes:
                nodes[c] = TreeNode(c)
            if left:
                nodes[p].left = nodes[c]
            else:
                nodes[p].right = nodes[c]
        # 寻找根节点
        root = -1
        for val, r in isRoot.items():
            if r:
                root = val
                break
        return nodes[root]

golang 解法, 执行用时: 316 ms, 内存消耗: 8 MB, 提交时间: 2022-11-19 18:22:28 

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func createBinaryTree(descriptions [][]int) *TreeNode {
	nodes := map[int]*TreeNode{}
	in := map[int]bool{}
	for _, d := range descriptions {
		x, y := d[0], d[1]
		if nodes[x] == nil {
			nodes[x] = &TreeNode{Val: x}
		}
		if nodes[y] == nil {
			nodes[y] = &TreeNode{Val: y}
		}
		if d[2] == 1 {
			nodes[x].Left = nodes[y]
		} else {
			nodes[x].Right = nodes[y]
		}
		in[y] = true
	}

	for i, node := range nodes {
		if !in[i] { // 入度为 0 则为根
			return node
		}
	}
	return nil
}

python3 解法, 执行用时: 532 ms, 内存消耗: 22.6 MB, 提交时间: 2022-11-19 18:22:14 

# 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)
        vals = set()
        for x, y, left in descriptions:
            if left:
                nodes[x].left = nodes[y]
            else:
                nodes[x].right = nodes[y]
            vals.add(y)
        for v, node in nodes.items():
            node.val = v
        return next(node for v, node in nodes.items() if v not in vals)

上一题

© 2024 leetcode.cn