对称二叉树

递归 树

递归

递归的玩法还是不够六啊，我是中序遍历看对称的方式做的

实际上这里递归已经有点不一样的味道了，主要是和经典树的遍历递归不一样，而是一种自由发挥的递归

/**
 * 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 isSymmetric(TreeNode* root) {
        if (root == nullptr) return true;
        return check(root->left, root->right);
    }
    bool check(TreeNode* p, TreeNode* q) {
        if(p == nullptr && q == nullptr) return true;
        else if (p != nullptr && q != nullptr) {
            return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);
        } else return false;
    }
};

他其实是两头走，两头同时走，可以用两个变量的方式实现两头同时走

递推

注意到，上面的递归函数是最后返回用递归，还记得吗？最后返回用递归的往往可以简单的改为递推

可以想象，我从一个队列中拿两个出来，一定是对应位置的比较，这要求我入队的时候，就得左右交替着入队