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

小松鼠
發佈於演算法專欄 個房間
閱讀時間約 4 分鐘

題目敘述

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


葉子節點都是真假值

0代表False

1代表True


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

2代表boolean OR operator

3代表boolean AND operator


原本的英文題目敘述


測試範例

Example 1:

raw-image


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

52會員
336內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
發表第一個留言支持創作者!