一魚再吃 用DFS來計算有幾條 偽回文路徑 Leetcode #1457

Denys Nevozhai on Unsplash

題目敘述

題目給定我們一顆二元樹的根節點，要求我們計算出從根節點到葉子節點的偽回文路徑路徑有幾條?

偽回文路徑路徑 的定義:

例如:

1 -> 3 -> 3

重新排列之後，可以形成

3 -> 1 -> 3 回文

從頭讀到尾是313

從尾讀到頭也是313

題目的原文敘述

測試範例

Example 1:

Input: root = [2,3,1,3,1,null,1]
Output: 2 
Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the red path [2,3,3], the green path [2,1,1], and the path [2,3,1]. Among these paths only red path and green path are pseudo-palindromic paths since the red path [2,3,3] can be rearranged in [3,2,3] (palindrome) and the green path [2,1,1] can be rearranged in [1,2,1] (palindrome).

2 -> 3 -> 3 可以重排成 3 -> 2 -> 3 回文
2 -> 1 -> 1 可以重排成 1 -> 2 -> 1 回文​

Example 2:

Input: root = [2,1,1,1,3,null,null,null,null,null,1]
Output: 1 
Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the green path [2,1,1], the path [2,1,3,1], and the path [2,1]. Among these paths only the green path is pseudo-palindromic since [2,1,1] can be rearranged in [1,2,1] (palindrome))

2 -> 1 -> 1 可以重排成 1 -> 2 -> 1 回文​。

Example 3:

Input: root = [9]
Output: 1

9 可以重排成 9 本身就是回文。

約束條件

Constraints:

• The number of nodes in the tree is in the range [1, 10^5].

節點總數目介於1 ~ 10^5 之間。

• 1 <= Node.val <= 9

每個節點的值一定介於1 ~ 9 之間。

演算法

這題的關鍵在於: 什麼條件，可以讓路徑重排之後形成回文?

那就回頭檢視回文具有怎樣的結構，或者說 回文具有怎樣的pattern？

其實，回文總共只有兩種結構。

第一種，具有中心元素的回文。

可以抽象化成 Head + Center + Tail，其中 Tail = Head的逆序(也就是彼此互為鏡像)

例如:

1 2 3 4 3 2 1, Head = 1 2 3, Center = 4, Tail=3 2 1

頭尾的元素一定都出現偶數次? 為什麼，因為彼此互為鏡像，一半的次數在Head，一半的次數在Tail。

只有Center 元素，4的出現次數是奇數次。

第二種，不具有中心元素的回文。

可以抽象化成 Head + Tail，其中 Tail = Head的逆序(也就是彼此互為鏡像)

例如:

1 2 3 3 2 1, Head = 1 2 3, Tail=3 2 1

頭尾的元素一定都出現偶數次? 為什麼，因為彼此互為鏡像，一半的次數在Head，一半的次數在Tail。

因此，到這邊，可以歸納出一個結論，要重新排列形成回文palindrome的話，最多只能有一個元素的出現次數是奇數次。

因次，我們可以用DFS去遞迴展開，從上到下探索整棵樹，檢查並且計算有幾條路徑滿足這個條件:

最多只能有一個元素的出現次數是奇數次。

在記錄出現次數的時候，我們使用toggle bit flag的技巧去紀錄數字1~數字9的出現次數。

凡是出現偶數次的數字，都會toggle bit偶數次，相當於做xor bit mask兩次，對應到的就是bit flag為0。

凡是出現奇數次的數字，都會toggle bit奇數次，相當於做xor bit mask一次，對應到的就是bit flag為1。

最後檢查每條從上到下的路徑所對應的bit flag (occurrence)有沒有滿足最多只能有一個元素的出現次數是奇數次即可。

程式碼

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:
        
        ## Parameter
        # node: tree node
        # occurrence: bit flag for number 1 ~ 9
        def check(node=None, occurrence=0):

            # Base case for empty tree
            if not node:
                return 0
            
            # Toggle bit flag for current node value
            occurrence ^= (1 << node.val)

            # Count pseudo palindromeic path in current tree
            palin_count = check(node.left, occurrence) + check(node.right, occurrence)
            
            if not node.left and not node.right:
                # Now, we are at leaf node, update pseudo palindromeic path count if at most one number has odd occurrence
                palin_count += ( (occurrence & occurrence-1) == 0 )

            return palin_count

        # ======================================
        return check(node=root, occurrence=0)

複雜度分析

時間複雜度:

從上到下用DFS探索整棵樹，檢查每條從樹根到葉子的路徑，所需時間為O(n)。

空間複雜度:

從上到下用DFS探索整棵樹，遞迴深度最深為O(n)，發生在整棵樹向左歪斜或向又歪斜的時候。

關鍵知識點

這題的關鍵在於: 什麼條件，可以讓路徑重排之後形成回文?

那就回頭檢視回文具有怎樣的結構，或者說 回文具有怎樣的pattern？

其實，回文總共只有兩種結構。

第一種，具有中心元素的回文，可以抽象化成 Head + Center + Tail。

第二種，不具有中心元素的回文，可以抽象化成 Head + Tail。

要重新排列形成回文palindrome的話，最多只能有一個元素的出現次數是奇數次。

Reference:

[1] Python O(n) by DFS // At most one number with odd occurrence. [w/ Simple proof]