- dfs 查询每条路径,空节点返回,
- 节点入路径
- 该节点左右均为空则进入回文判断逻辑
- 加上左右节点所在路径伪回文路径数
- 该节点查询完毕,将其从路径中清除,回溯到上一节点
- 引用传参,避免了多次参数的复制,同时通过回溯状态参与上一分支的查询
- 返回伪回文路径数
class Solution {
public:int dfs(vector<int>& micpaths, TreeNode* root){if(!root)return 0;micpaths[root->val]++;int ret = 0;if(!root->left && !root->right){ret = check_palindromic(micpaths);}int l = dfs(micpaths, root->left);int r = dfs(micpaths, root->right);micpaths[root->val]--;return ret + l + r;}bool check_palindromic(const vector<int>& count){int odd = 0;for(auto & a : count){if(a & 1) odd++;}return odd <= 1;}int pseudoPalindromicPaths (TreeNode* root) {vector<int> micpaths(10);return dfs(micpaths, root);}
};