Leetcode 2196 - Create Binary Tree From Descriptions

題目

Problem#

題目給你一堆邊 edges = [parent, child, isLeft] 要你回傳建出來的圖。
isLeft==1 代表 child 是 parent 的左子節點；反之 isLeft==0，代表 child 是 parent 的右子節點。

• E = edges
• 1 <= E.length <= 104
• E[i].length == 3
• 1 <= parent, child <= 105
• 0 <= isLeft <= 1

想法#

照邊把圖建起來，要維護目前出現過的點，方便存取建圖。

• 如何找根(Root)節點?
  • 根節點不是其他任何其他節點子節點
  • 維護一個 set，先把所有點加入，假如當過 child 就從中刪除，最後就剩下根節點
• 時間複雜度: $\mathcal{O}(E logE)$
• 空間複雜度: $\mathcal{O}(E)$

AC Code#

賞析#

• 先建好左子樹和右子樹的表和每個節點當過child的次數的表，找到 root 再建樹
  • https://pastebin.com/8kmCuGZX

心得#

在賽中一開始還卡我 map = =，這不是 leetcode ㄇQQ