一魚再吃 用DFS來計算有幾條 偽回文路徑 Leetcode #1457
題目敘述
題目給定我們一顆二元樹的根節點，要求我們計算出從根節點到葉子節點的偽回文路徑路徑有幾條?
偽回文路徑路徑 的定義:
路徑經過重新排列之後，可以形成回文Palindrome，也就是頭尾鏡像對稱。
例如:
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]
