2196. Create Binary Tree From Descriptions

Problem

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 <= 10^4

• descriptions[i].length == 3

• 1 <= parenti, childi <= 10^5

• 0 <= isLefti <= 1

• The binary tree described by descriptions is valid.

Solution (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) {
        Map<Integer, Data> map = new HashMap<>();
        for (int[] description : descriptions) {
            Data data = map.get(description[0]);
            if (data == null) {
                data = new Data();
                data.node = new TreeNode(description[0]);
                data.isHead = true;
                map.put(description[0], data);
            }
            Data childData = map.get(description[1]);
            if (childData == null) {
                childData = new Data();
                childData.node = new TreeNode(description[1]);
                map.put(childData.node.val, childData);
            }
            childData.isHead = false;
            if (description[2] == 1) {
                data.node.left = childData.node;
            } else {
                data.node.right = childData.node;
            }
        }
        for (Map.Entry<Integer, Data> entry : map.entrySet()) {
            if (entry.getValue().isHead) {
                return entry.getValue().node;
            }
        }
        return null;
    }

    private static class Data {
        TreeNode node;
        boolean isHead;
    }
}

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).