圖論應用:從從屬關係重建二元樹_Leetcode #2196

Verne Ho on Unsplash

題目敘述 Create Binary Tree From Descriptions

給定一個輸入陣列，每一個tuple代表節點之間了從屬關係。
請從從屬關係重建整顆二元樹，並且返回整顆二元樹的根結點。

測試範例

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

輸入陣列的長度介於1~一萬。

• descriptions[i].length == 3

每條描述包含三個資訊: 父節點，子節點，左右方向。

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

父節點、子節點節點值介於1~十萬之間。

• 0 <= isLefti <= 1

isLeft=1代表是左邊的子節點，反之，代表右邊的子節點。

• The binary tree described by descriptions is 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)

Reference:

[1] Create Binary Tree From Descriptions - LeetCode