[閒聊] 每日LeetCode
1457. Pseudo-Palindromic Paths in a Binary Tree
題目：
給定一個Tree找出根節點到葉節點的所有Path中元素可以排列成迴文的Path數量。
思路：
使用回溯法來遞迴Tree，遞迴的過程統計數字0~9的出現次數，當遇到葉子節點時
判斷元素數量是否最多只有一個是奇數，若是則res+1。
Code：
class Solution {
int res = 0;
public int pseudoPalindromicPaths (TreeNode root) {
int[] count = new int[10];
DFS(root, count);
return res;
}
private void DFS(TreeNode root, int[] count) {
if(root == null) return;
count[root.val]++;
DFS(root.left, count);
if(root.left == null && root.right == null) {
int odd = 0;
for(int i = 1;i < 10 && odd < 2; i++)
if (count[i] % 2 != 0)
odd++;
if(odd < 2) res++;
}
DFS(root.right, count);
count[root.val]--;
}
}
--
Lycoris Recoil 好評放送中
https://i.imgur.com/DCuHAOv.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 115.165.253.177 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1663167753.A.4E9.html
推
09/14 23:05,
1年前
, 1F
09/14 23:05, 1F
→
09/15 08:05,
1年前
, 2F
09/15 08:05, 2F
→
09/15 12:41,
1年前
, 3F
09/15 12:41, 3F
討論串 (同標題文章)
完整討論串 (本文為第 1 之 719 篇)：
閒聊
1
3