[閒聊] 每日LeetCode

[Rushia (みけねこ的鼻屎)]

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
https://i.imgur.com/H7pqOEl.jpg
https://imgur.com/n0zRQAj.gif
https://i.imgur.com/ug3QV1r.gif

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 115.165.253.177 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1663167753.A.4E9.html
推 Poshintow: 說人話                                       對不起
→ abcd991276: 迴文是什麼
→ Zain3535: 迴文就是像這種->abcdcba或abcddcba