微計算機 布林代數的二元樹_Leetcode #2331

Vishnu Mohanan on Unsplash

題目敘述

題目給定一個布林代數的二元樹，要求我們計算最後的結果。

葉子節點都是真假值

0代表False

1代表True

非葉子節點都是布林運算子

2代表boolean OR operator

3代表boolean AND operator

原本的英文題目敘述

測試範例

Example 1:

Input: root = [2,1,3,null,null,0,1]
Output: true
Explanation: The above diagram illustrates the evaluation process.
The AND node evaluates to False AND True = False.
The OR node evaluates to True OR False = True.
The root node evaluates to True, so we return true.

Example 2:

Input: root = [0]
Output: false
Explanation: The root node is a leaf node and it evaluates to false, so we return false.

約束條件

Constraints:

• The number of nodes in the tree is in the range [1, 1000].

節點總數目介於1~1000。

題目保證輸入不是空樹。

• 0 <= Node.val <= 3

節點值都介於0~3之間。

• Every node has either 0 or 2 children.

每個節點有0個或2個子節點。

• Leaf nodes have a value of 0 or 1.

葉子節點的節點值一定是0或1。

• Non-leaf nodes have a value of 2 or 3.

非葉子節點的節點值一定是2或3。

演算法 DFS + 布林代數模擬

抽象的想，每一次計算都可以這樣表達。

       布林運算子
       /      \​
   真假值     真假值

如果自己是葉子節點，直接返回真假值(True / False)

如果自己不是葉子節點，
則根據子節點回傳的真假值(True/False)進行指定的布林運算(OR/AND)

程式碼 DFS + 布林代數模擬

class Solution:
    def evaluateTree(self, root: Optional[TreeNode]) -> bool:

        #F, T, OR, AND = 0, 1, 2, 3

        ## Leaf node with boolean value
        if root.val in (0, 1):
            return root.val

        ## Non-leaf node with boolean operator
        elif root.val == 2:
            return self.evaluateTree(root.left) | self.evaluateTree(root.right)

        else:
            return self.evaluateTree(root.left) & self.evaluateTree(root.right)

或者，額外根據計算結果進行化簡

class Solution:
    def evaluateTree(self, root: Optional[TreeNode]) -> bool:

        #F, T, OR, AND = 0, 1, 2, 3

        ## Leaf node with boolean value
        if root.val in (0, 1):
            return root.val

        return ( self.evaluateTree(root.left) + self.evaluateTree(root.right) ) > (root.val-2)

複雜度分析

時間複雜度: O(n )

DFS拜訪整棵樹，每個節點至多拜訪一次。

空間複雜度: O(n )

DFS拜訪整棵樹，當整棵樹向左歪斜或向右歪斜時。有最大深度O(n)。

關鍵知識點

相當於布林代數的計算樹，根據定義好的計算規則進行模擬即可。

Reference

[1] Evaluate Boolean Binary Tree - LeetCode