根据描述创建二叉树

标签: 树 深度优先搜索 广度优先搜索 数组 哈希表 二叉树

难度: Medium

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

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

请你根据 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 的节点，因为它没有父节点。 
结果二叉树如上图所示。

提示：

  • 1 <= descriptions.length <= 104
  • descriptions[i].length == 3
  • 1 <= parenti, childi <= 105
  • 0 <= isLefti <= 1
  • descriptions 所描述的二叉树是一棵有效二叉树

Submission

运行时间: 325 ms

内存: 23.8 MB

# 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 = {}
        node = {}
        for part,child,left in descriptions:
            if part not in isRoot:
                isRoot[part] = True
            isRoot[child] = False
            if part not in node:
                node[part] = TreeNode(part)
            if child not in node:
                node[child] = TreeNode(child)

            if left:
                node[part].left = node[child]
            else:
                node[part].right = node[child]
        root = -1
        for key, val in isRoot.items():
            if val:
                root = key
                break
        return node[root]

Explain

此题解首先通过遍历给定的描述数组来构造二叉树。针对每个描述项 [parenti, childi, isLefti]，如果 parenti 和 childi 在之前未曾创建，则创建相应的 TreeNode 对象，并存储在一个字典中，以节点的值作为键。另外，还用一个字典来标记每个节点是否可能是根节点，即如果一个节点作为 child 出现过，那么它就不可能是根节点。最后，遍历这个可能的根节点的字典，找到唯一的标记为 True 的节点，即为根节点。

时间复杂度: O(n)

空间复杂度: O(n)

# 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 = {}  # 字典用于标记每个节点是否可能是根节点
        node = {}  # 存储节点值到TreeNode对象的映射
        for part, child, left in descriptions:
            if part not in isRoot:
                isRoot[part] = True  # 假设每个parent一开始可能是根节点
            isRoot[child] = False  # 出现作为child的节点不可能是根节点
            if part not in node:
                node[part] = TreeNode(part)  # 如果节点不存在，则创建新节点
            if child not in node:
                node[child] = TreeNode(child)

            if left:
                node[part].left = node[child]  # 根据isLeft标记设置左或右子节点
            else:
                node[part].right = node[child]
        root = -1
        for key, val in isRoot.items():
            if val:  # 寻找可能的根节点
                root = key
                break
        return node[root]  # 返回构造的树的根节点

Explore

在构建二叉树的过程中，如果某个节点多次被标记为同一子节点（即多次被标记为左子节点或右子节点），那么后面的标记将覆盖前面的标记。这是因为题解中的算法采用的是直接赋值的方式来设置子节点，没有进行是否已经设置的检查。这可能导致数据不一致或者逻辑错误，特别是在输入数据有误的情况下。

题解中通过一个字典`isRoot`来标记每个节点是否可能是根节点，初始假设每个节点都可能是根节点，但如果一个节点作为任何其他节点的子节点出现，就将其标记为不可能是根节点。最后检查`isRoot`字典，寻找标记为True的节点即可确定根节点。如果理论上出现多个节点未被作为子节点引用，那么将违反二叉树的定义（一个树只能有一个根节点）。在实际实现中，如果发现有多个可能的根节点，应该抛出异常或错误，提示输入数据可能有误。

在处理每个节点对时，需要检查节点是否已经在字典中存在，以避免重复创建相同的节点。这是因为可能多次引用同一个节点（作为不同节点的子节点或多次引用作为父节点），如果不进行这种检查，就会创建多个具有相同值的节点实例，这会导致数据结构的不正确和资源的浪费。这一步骤会稍微增加计算开销，因为每次插入都需要检查字典，但由于字典的查找和插入操作平均时间复杂度为O(1)，因此对整体算法效率的影响是可控的。

题解中的查找根节点的方法是通过一个遍历`isRoot`字典来寻找标记为True的节点。虽然这种方法简单明了，但在最坏情况下需要遍历整个字典。一种可能的优化方法是在构造过程中直接维护一个可能的根节点列表，每次修改节点的根节点属性时更新这个列表。但是，这种方法需要额外的逻辑来管理列表，可能会增加实现的复杂性。因此，当前的方法在大多数情况下已经足够高效，特别是考虑到二叉树通常节点数量不会特别大。