🔗 🟢 2331. Evaluate Boolean Binary Tree 1304

tags: `Biweekly Contest 82` `遞迴(Recursion)`

題意

給定一個 Full Binary Tree 的根，每個節點的值為 $[0, 1, 2, 3]$ ，其中 $0$ 表示 False， $1$ 表示 True， $2$ 表示 OR， $3$ 表示 AND。且 $0$ 和 $1$ 只會出現在葉節點， $2$ 和 $3$ 只會出現在非葉節點。

返回這個樹的布林運算結果。

思路：遞迴(Recursion)

這是一個簡單的遞迴問題，只要根據每個節點的值判斷屬於 Operator ( AND / OR ) 或 Operand ( True / False ) ，若為 Operand 則直接返回其值，若為 Operator 則根據其值來遞迴計算左右子樹的值即可。

由於 AND / OR 都是 Binary Operator，所以這是一棵 Full Binary Tree，也就是除了樹葉以外，每個節點都有兩個child，因此在判斷是否為Leaf時只要判斷一邊就好。

此外，由於可能可以提前短路，所以不用先計算左右子樹的值。

複雜度分析

時間複雜度： $O(n)$ 。
空間複雜度： $O(n)$ ，遞迴所使用的Stack空間。

class Solution:
    def evaluateTree(self, root: Optional[TreeNode]) -> bool:
        # if not root.left and not root.right: # if leaf node
        if not root.left: # 只要判斷一邊就好
            return root.val == 1
        if root.val == 3: # 由於可能可以提前短路，所以不用先計算左右子樹的值
            return self.evaluateTree(root.left) and self.evaluateTree(root.right)
        else:
            return self.evaluateTree(root.left) or self.evaluateTree(root.right)

class Solution {
public:
    bool evaluateTree(TreeNode* root) {
        if (root->left == nullptr) {
            return root->val;
        }
        if (root->val == 3) return evaluateTree(root->left) && evaluateTree(root->right);
        else return evaluateTree(root->left) || evaluateTree(root->right);
    }
};