[LeetCode] 2196. Create Binary Tree From Descriptions

You are given a 2D integer array descriptions where descriptions[i] = [parenti, childi, isLefti] indicates that parenti is the parent of childi in a binary tree of unique values. Furthermore,
If isLefti == 1, then childi is the left child of parenti.
If isLefti == 0, then childi is the right child of parenti.
Construct the binary tree described by descriptions and return its root.

The test cases will be generated such that the binary tree is valid.

Example 1:

Input: descriptions = [[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]]
Output: [50,20,80,15,17,19]
Explanation: The root node is the node with value 50 since it has no parent.
The resulting binary tree is shown in the diagram.

Example 2:

Input: descriptions = [[1,2,1],[2,3,0],[3,4,1]]
Output: [1,2,null,null,3,4]
Explanation: The root node is the node with value 1 since it has no parent.
The resulting binary tree is shown in the diagram.

Constraints:
1 <= descriptions.length <= 104
descriptions[i].length == 3
1 <= parent, child <= 105
0 <= isLeft <= 1
The binary tree described by descriptions is valid.

根据描述创建二叉树。

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

如果 isLeft == 1 ，那么 child 就是 parent 的左子节点。
如果 isLeft == 0 ，那么 child 就是 parent 的右子节点。
请你根据 descriptions 的描述来构造二叉树并返回其 根节点 。

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

思路

思路是哈希表 + 模拟。遍历 input 数组，因为题目说了二叉树中各节点的值互不相同，所以这里我们可以用一个哈希表记录<node val, TreeNode>的关系。因为每个 description 展示的是两个 node 之间的关系，所以在用哈希表存好<node val, TreeNode>之后，我们还可以连接这两个节点，以保存节点之间的父子关系。

这里同时我用了一个 visited 数组，记录所有遍历到的 child 节点。最后我再次遍历这个 visited 数组的时候，唯一一个没有被遍历到的值就是根节点的值 root.val，所以最后返回的是 map.get(root.val) 就是根节点。

复杂度

时间O(n)
空间O(n)

代码

Java实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode createBinaryTree(int[][] descriptions) {
		HashMap<Integer, TreeNode> map = new HashMap<>();
		int[] visited = new int[100001];
		for (int i = 0; i < descriptions.length; i++) {
			int parent = descriptions[i][0];
			int child = descriptions[i][1];
			int isLeft = descriptions[i][2];
			if (!map.containsKey(parent)) {
				TreeNode node = new TreeNode(parent);
				map.put(parent, node);
			}
			if (!map.containsKey(child)) {
				TreeNode node = new TreeNode(child);
				map.put(child, node);
			}
			
			// build parent, child relationship
			TreeNode p = map.get(parent);
			TreeNode c = map.get(child);
			// visited数组记录所有遍历过的child node
			visited[child] = 1;
			if (isLeft == 1) {
				p.left = c;
			} else {
				p.right = c;
			}
		}

		TreeNode root = new TreeNode();
		for (Integer i : map.keySet()) {
			if (visited[i] == 0) {
				root = map.get(i);
				return root;
			}
		}
		return null;
    }
}