[Leetcode] Create Binary Tree From Descriptions(Medium)

發表於： 分類於：
字數： 548 閱讀：≈ 2分鐘 瀏覽：

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

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.

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.

How can we solve this problem?

這是給定一個2維的Array,根據Array[i]建構一棵Binary tree。主要得問題是哪一個是成為Tree root呢?要怎麼知道有哪些Child Node呢?

  • 我們透過Map來幫助我們記錄所有Child Node,以便之後的建構
  • 因每個Child Node都必須有一個Parent Node,也就是說在Map中能找到的Node必定是有Parent的，當找到1個Node沒有在Map中，也就代表著該Node必定是整棵Binary Tree的Head。
    根據1跟2的邏輯,並使用一個Loop來建構Binary Tree即可。

Solution: 

/**
 * 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>>& des) {
        unordered_map<int,TreeNode*> m;
        TreeNode* head = nullptr;

        //creating all node ->child node
        for(int i = 0;i<des.size();i++)
            m[des[i][1]] = new TreeNode(des[i][1]); // all child node,except head node
        
        for(int i = 0;i<des.size();i++){
            //getting root node from map
            if(m.find(des[i][0]) == m.end()){ //getting head node
                TreeNode* root = new TreeNode(des[i][0]);
                head = root;
                m[des[i][0]] = root;
            }
            if(des[i][2]){
                m[des[i][0]]->left = m.find(des[i][1]) == m.end() ? new TreeNode(des[i][1]) : m[des[i][1]];
            }else {
                m[des[i][0]]->right = m.find(des[i][1]) == m.end() ? new TreeNode(des[i][1]) : m[des[i][1]];;   
            }
        }
        return head;
    }
};