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 <= 10^4
  • descriptions[i].length == 3
  • 1 <= parenti, childi <= 10^5
  • 0 <= isLefti <= 1
  • descriptions 描述的二叉树是有效的

解题思路

解题思路

这道题的核心是根据父子关系描述构建二叉树。我们可以采用哈希表的方法来解决：

主要步骤：

  1. 创建节点映射：使用哈希表存储所有节点值到TreeNode的映射，确保每个值只创建一个节点
  2. 建立父子关系：遍历描述数组，根据isLeft标志建立父子连接关系
  3. 找到根节点：根节点的特征是它不是任何节点的子节点，可以通过记录所有子节点来找到根节点

算法细节：

  • 使用nodeMap存储值到节点的映射，避免重复创建节点
  • 使用children集合记录所有作为子节点的值
  • 遍历descriptions，对每个描述：
    • 确保父节点和子节点都存在于nodeMap中
    • 根据isLeft值建立左子或右子关系
    • 将子节点值加入children集合
  • 最后遍历nodeMap，找到不在children集合中的节点作为根节点

这种方法时间复杂度为O(n)，空间复杂度为O(n)，其中n是descriptions的长度。

代码实现

class Solution {
public:
    TreeNode* createBinaryTree(vector<vector<int>>& descriptions) {
        unordered_map<int, TreeNode*> nodeMap;
        unordered_set<int> children;
        
        // 遍历描述，创建节点并建立关系
        for (auto& desc : descriptions) {
            int parent = desc[0], child = desc[1], isLeft = desc[2];
            
            // 确保父节点存在
            if (nodeMap.find(parent) == nodeMap.end()) {
                nodeMap[parent] = new TreeNode(parent);
            }
            
            // 确保子节点存在
            if (nodeMap.find(child) == nodeMap.end()) {
                nodeMap[child] = new TreeNode(child);
            }
            
            // 建立父子关系
            if (isLeft == 1) {
                nodeMap[parent]->left = nodeMap[child];
            } else {
                nodeMap[parent]->right = nodeMap[child];
            }
            
            // 记录子节点
            children.insert(child);
        }
        
        // 找到根节点（不是任何节点的子节点）
        for (auto& pair : nodeMap) {
            if (children.find(pair.first) == children.end()) {
                return pair.second;
            }
        }
        
        return nullptr;
    }
};

class Solution:
    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:
        node_map = {}
        children = set()
        
        # 遍历描述，创建节点并建立关系
        for parent, child, is_left in descriptions:
            # 确保父节点存在
            if parent not in node_map:
                node_map[parent] = TreeNode(parent)
            
            # 确保子节点存在
            if child not in node_map:
                node_map[child] = TreeNode(child)
            
            # 建立父子关系
            if is_left == 1:
                node_map[parent].left = node_map[child]
            else:
                node_map[parent].right = node_map[child]
            
            # 记录子节点
            children.add(child)
        
        # 找到根节点（不是任何节点的子节点）
        for val in node_map:
            if val not in children:
                return node_map[val]
        
        return None

public class Solution {
    public TreeNode CreateBinaryTree(int[][] descriptions) {
        Dictionary<int, TreeNode> nodeMap = new Dictionary<int, TreeNode>();
        HashSet<int> children = new HashSet<int>();
        
        // 遍历描述，创建节点并建立关系
        foreach (var desc in descriptions) {
            int parent = desc[0], child = desc[1], isLeft = desc[2];
            
            // 确保父节点存在
            if (!nodeMap.ContainsKey(parent)) {
                nodeMap[parent] = new TreeNode(parent);
            }
            
            // 确保子节点存在
            if (!nodeMap.ContainsKey(child)) {
                nodeMap[child] = new TreeNode(child);
            }
            
            // 建立父子关系
            if (isLeft == 1) {
                nodeMap[parent].left = nodeMap[child];
            } else {
                nodeMap[parent].right = nodeMap[child];
            }
            
            // 记录子节点
            children.Add(child);
        }
        
        // 找到根节点（不是任何节点的子节点）
        foreach (var kvp in nodeMap) {
            if (!children.Contains(kvp.Key)) {
                return kvp.Value;
            }
        }
        
        return null;
    }
}

var createBinaryTree = function(descriptions) {
    const nodeMap = new Map();
    const children = new Set();
    
    for (const [parent, child, isLeft] of descriptions) {
        if (!nodeMap.has(parent)) {
            nodeMap.set(parent, new TreeNode(parent));
        }
        if (!nodeMap.has(child)) {
            nodeMap.set(child, new TreeNode(child));
        }
        
        const parentNode = nodeMap.get(parent);
        const childNode = nodeMap.get(child);
        
        if (isLeft) {
            parentNode.left = childNode;
        } else {
            parentNode.right = childNode;
        }
        
        children.add(child);
    }
    
    for (const [parent] of descriptions) {
        if (!children.has(parent)) {
            return nodeMap.get(parent);
        }
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n) - 其中n是descriptions数组的长度，需要遍历一次descriptions数组创建节点和关系，然后遍历nodeMap找根节点
空间复杂度O(n) - 需要哈希表存储所有节点，以及集合存储所有子节点值，最坏情况下存储n个节点

相关题目