LC 1457. Pseudo-Palindromic Paths in a Binary Tree

https://leetcode.com/problems/pseudo-palindromic-paths-in-a-binary-tree/description/

class Solution {
public:
    int ans;

    void dfs(TreeNode *cur, vector<int> &cnt) {
        if (cur == NULL) return;
        cnt[cur -> val] += 1;
        dfs(cur -> left, cnt);
        dfs(cur -> right, cnt);
        if ((cur -> left == NULL) && (cur -> right == NULL)) {
            int odd = 0;
            for (auto &x: cnt) odd += x % 2;
            if (odd <= 1) ans += 1;
        }
        cnt[cur -> val] -= 1;
    }

    int pseudoPalindromicPaths (TreeNode* root) {
        ans = 0;
        vector<int> cnt(10, 0);
        dfs(root, cnt);
        return ans;
    }
};

這裡你們可以感受到一點 Backtracking 的感覺，也就是在往下 DFS 前我們會先做加 1 的動做，並且在回去之前會再把這個進行減 1 的動作。

Backtracking 在 top-down 的 DP 當中也算是挺常用到的技巧