1. 二叉树的伪回文途径

二叉树的伪回文途径。本道题需求咱们处理两个问题，怎么保存每一条从根节点到叶子节点的途径？怎么判别这条途径上的节点是否是一个伪回文途径？针对以上两个问题，咱们逐个处理。

1.1 给定一个序列怎么判别它是一个伪回文途径？

首先，伪回文途径便是当给定序列的所有排列中有一个是回文序列，则该序列便是伪回文途径。关于一个回文序列，从中心剖开，它是对称的。一个回文序列至多呈现一个元素个数为奇数的元素。 所以咱们只需求遍历序列，计算每个元素的呈现频率，当呈现两个奇数个元素的时分，该序列必定不是伪回文序列。代码如下：

bool isValid(vector<int>& nums) {
        /*运用map记载元素个数*/
        unordered_map<int, int> cnt;
        for(auto i : nums) {
            cnt[i]  ;
        }
        int flag = 0;
        /*遍历map，统计奇数个元素的个数*/
        for(auto ite : cnt) {
            if(ite.second % 2 == 1) flag  ;
        }
        return flag > 1 ? false : true;
}

1.2 怎么保存树中的一条途径？

途径的界说是：从根节点到叶子节点上节点的序列。咱们需求一边遍历树，一边保存遍历过的节点。咱们运用一个全局变量记载满足条件的途径。在递归遍历的时分，vector<int>来记载元素，需求注意的是，这儿运用的是值传递。

int count = 0;
void backtrack(TreeNode* root, vector<int> path) {
    /*必须是叶子节点，而不是遇到空节点*/
    if(root == nullptr) return;
    path.push_back(root->val);
    /*遇到叶子节点，则判别途径是否是伪回文途径*/
    if(!root->left && !root->right) {
        if(isValid(path)) count  ;
        return;
    }
    backtrack(root->left, path);
    backtrack(root->right, path);
}
int pseudoPalindromicPaths (TreeNode* root) {
    vector<int> v;
    backtrack(root, v);
    return count;
}

这种做法从正确性上来说，现已能够处理这道题了。但是由于运用的是值传递（能够避免pop操作），关于比较长的测试数据会超时，没有办法全部通过测试用例。

2. 二叉树的所有途径

本题目是leetcode257题。从题目的思路上来说，与上一题是类似的，甚至是更简略。由于咱们只需求做好元素的保存就能够。我先直接放出代码。

class Solution {
public:
    /*全局变量，用来保存成果*/
    vector<string> result;
    void backtrack(TreeNode* root, string str) {
        /*遇到空节点就回来，遇到叶子节点再做处理*/
        if(root == nullptr) return;
        if(!root->left && !root->right) {
            str  = to_string(root->val);
            result.push_back(str);
        }
        str  = to_string(root->val)   "->";
        backtrack(root->left, str);
        backtrack(root->right, str);
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        string str;
        backtrack(root, str);
        return result;
    }
};

需求强调的是，代码中每次都是处理当前层节点的元素，递归过程中也没有对子节点为空的判别，而是到了下一层再做处理。如果是空节点直接回来，是叶子节点则保存成果。传递的过程中同样运用的是值传递。 再来对比一下我原先的做法：

class Solution {
public:
    void searchTrace(TreeNode* curr, vector<int>& path, vector<string>& result) {
        /*把当前层节点保存到path中*/
        path.push_back(curr->val);
        /*当前节点是叶子节点，则开始处理途径上的节点，并保存*/
        if(curr->left == nullptr && curr->right == nullptr) {
            string tmp;
            for(int i = 0; i < path.size() - 1; i  ) {
                tmp  = to_string(path[i]);
                tmp  = "->";
            }
            tmp  = to_string(path[path.size()-1]);
            result.push_back(tmp);
            return;
        }
        /* 递归拜访之前，做了非空判别
         * 且path传递的是引证，所以每次递归回来都需求对元素进行pop
         */
        if(curr->left) {
            searchTrace(curr->left, path, result);
            path.pop_back();
        }
        if(curr->right) {
            searchTrace(curr->right, path, result);
            path.pop_back();
        }
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<int> path;
        vector<string> result;
        searchTrace(root, path, result);
        return result;
    }
};

3. 上面两种不同的保存元素的做法中我困惑的点

关于递归中采用值传递来保存元素的做法非常易于了解，且形式和一般的树的递归遍历方法相像。但有些题目无法运用。当值传递的类型是vector<int>，值传递就很容易超时或者超出了内存限制。比方关于第一题，我做出如下修正：

 * 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:
    bool isValid(vector<int>& nums) {
        unordered_map<int, int> cnt;
        for(auto i : nums) {
            cnt[i]  ;
        }
        int flag = 0;
        for(auto ite : cnt) {
            if(ite.second % 2 == 1) flag  ;
        }
        return flag > 1 ? false : true;
    }
    int count = 0;
    void backtrack(TreeNode* root, vector<int>& path) {
        /*必须是叶子节点，而不是遇到空节点*/
        if(root == nullptr) return;
        path.push_back(root->val);
        if(!root->left && !root->right) {
            if(isValid(path)) count  ;
            return;
        }
        /*由于是引证传递，每次递归回来，都需求pop元素*/
        backtrack(root->left, path);
        path.pop_back();
        backtrack(root->right, path);
        path.pop_back();
    }
    int pseudoPalindromicPaths (TreeNode* root) {
        vector<int> v;
        backtrack(root, v);
        return count;
    }
};

针对本来的值传递超时的问题，我把函数修正为引证传递，且每次递归子树回来都添加了pop操作来弹出元素，但成果还是过错的。比方针对以下这颗树：

以上代码给出的成果是3，而不是1。这是由于我的代码并没有对子节点做非空判别，而是鄙人一层做空判别并直接回来。关于叶子节点没有任何问题，但是关于有单个子节点为空的节点就会形成误判。比方在上面这颗树中，当遍历到这儿时

此刻遍历3的左子树为空并回来，注意此刻并没有在path中参加节点。回来后误弹出了3这个元素。path中的元素变为[2, 1]，再遍历右子树1这个节点的时分，就判定为伪回文序列。简略来说，由于回来的情况有两种，其中一种情况会在没有参加任何子节点的情况下回来，回来后又弹出元素，形成误判。咱们需求做的修正便是，只在子节点非空的情况下再做递归，一起删去开头的判别为空if语句。代码修正为以下：

 * 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:
    bool isValid(vector<int>& nums) {
        unordered_map<int, int> cnt;
        for(auto i : nums) {
            cnt[i]  ;
        }
        int flag = 0;
        for(auto ite : cnt) {
            if(ite.second % 2 == 1) flag  ;
        }
        return flag > 1 ? false : true;
    }
    int count = 0;
    void backtrack(TreeNode* root, vector<int>& path) {
        /*必须是叶子节点，而不是遇到空节点*/
        path.push_back(root->val);
        if(!root->left && !root->right) {
            if(isValid(path)) count  ;
            return;
        }
        if(root->left) {
            backtrack(root->left, path);
            path.pop_back();
        }
        if(root->right) {
            backtrack(root->right, path);
            path.pop_back();
        }
    }
    int pseudoPalindromicPaths (TreeNode* root) {
        vector<int> v;
        backtrack(root, v);
        return count;
    }
};

当然了以上的代码仍然有个别用例超时，还需求改动贮存的具体方案。