Last Updated on 2022-09-14 by Clay
題目
Given a binary tree where node values are digits from 1 to 9. A path in the binary tree is said to be pseudo-palindromic if at least one permutation of the node values in the path is a palindrome.
Return the number of pseudo-palindromic paths going from the root node to leaf nodes.
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).
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).
Example 3:
Input: root = [9] Output: 1
題目給定一個二元樹結構的根節點，我們需要計算在二元樹的走訪路徑中，究竟有多少條路徑走到底部時，節點中的值可以排列成『回文』。
比方說，[2, 3, 3] 可以被排列成 [3, 2, 3]，所以這就是一條回文的路徑（path）。
解題思路
DFS 深度優先搜索
要依序把樹狀結構每條路徑走到底，我們自然就是使用 DFS 來實作。而在走訪到樹底部時，我們還需要判斷這條路徑上的節點值是否可以組成回文。
可以組成回文的數值陣列有個特徵：每個數值的數量為奇數的數量最多最多可以是『一次』；換句話說，如果一個數值陣列中的有兩個數值出現的次數皆為奇數，則無論如何都無法組成回文。
所以在走訪的過程中，我還另外提出了一個 currPath 的陣列儲存數值出現的次數。從題目的規定來看，數值最大只能到 9，是故可以只開 10 個儲存空間的陣列儲存。
DFS 深度優先搜索複雜度
因為陣列的儲存空間我們可以預估為最多就是存十個數值，故為常數。
| Time complexity | O(n) |
| Space complexity | O(1) |
C++ 範例程式碼
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void DFS(int& palindromeNum, TreeNode* root, vector<int>& currPath) {
++currPath[root->val];
int odd = 0;
if (root->left != nullptr) {
DFS(palindromeNum, root->left, currPath);
}
if (root->right != nullptr) {
DFS(palindromeNum, root->right, currPath);
}
if (root->left == nullptr && root->right == nullptr) {
// Count odd number
for (int& n: currPath) {
odd += n % 2;
}
if (odd <= 1) {
++palindromeNum;
}
}
--currPath[root->val];
}
int pseudoPalindromicPaths (TreeNode* root) {
int palindromeNum = 0;
vector<int> v(10, 0);
DFS(palindromeNum, root, v);
return palindromeNum;
}
};Python 範例程式碼
# 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 __init__(self):
self.results = 0
self.currPath = [0 for _ in range(10)]
def dfs(self, root):
self.currPath[root.val] += 1
if root.left is not None:
self.dfs(root.left)
if root.right is not None:
self.dfs(root.right)
if (root.left is None and root.right is None):
count = 0
for n in self.currPath:
count += n % 2
if count <= 1:
self.results += 1
self.currPath[root.val] -= 1
def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:
self.dfs(root)
return self.results