題目敘述 Create Binary Tree From Descriptions
給定一個輸入陣列，每一個tuple代表節點之間了從屬關係。
請從從屬關係重建整顆二元樹，並且返回整顆二元樹的根結點。
測試範例
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
輸入陣列的長度介於1~一萬。
descriptions[i].length == 3
每條描述包含三個資訊: 父節點，子節點，左右方向。
1 <= parenti, childi<= 10^5
父節點、子節點節點值介於1~十萬之間。
0 <= isLefti<= 1
isLeft=1代表是左邊的子節點，反之，代表右邊的子節點。
- The binary tree described by
descriptionsis valid.
題目保證描述資訊都為真，可以重建一棵合法的二元樹。
演算法 重建二元樹
每個輸入都會提供兩個節點之間的從屬關係，
根據從屬關係建立父節點與子節點的連結。
最後掃描整顆樹，沒有當過子節點的就是整顆二元樹的根結點。
程式碼 重建二元樹
class Solution:
def createBinaryTree(self, descriptions):
children = set()
tree = {}
for p,c,is_left in descriptions:
parend_node = tree.setdefault(p, TreeNode(p))
child_node = tree.setdefault(c, TreeNode(c))
if is_left:
parend_node.left = child_node
else:
parend_node.right = child_node
children.add(c)
root = (set(tree) - set(children)).pop()
return tree[root]
複雜度分析
時間複雜度:O(n)
依序掃描每一個從屬關係，所需時間為O(n)。
空間複雜度:O(n)
需要建立字典和集合去儲存整顆樹，所需空間為O(n)
