題目敘述
題目給定一個布林代數的二元樹，要求我們計算最後的結果。
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
0or2children.
每個節點有0個或2個子節點。
- Leaf nodes have a value of
0or1.
葉子節點的節點值一定是0或1。
- Non-leaf nodes have a value of
2or3.
非葉子節點的節點值一定是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)。
關鍵知識點
相當於布林代數的計算樹，根據定義好的計算規則進行模擬即可。
