对称二叉树

例如下：
    1
   / \
  2   2
 / \ / \
3  4 4  3

将左子树看成一颗新的树
将右子树看成一颗新的树
左右两树轴对称
首先在中心位置的root不管
看左子树的根与右子树的根是否值相同
检查左子树的左子树右子树的右子树
检查左子树的右子树右子树的左子树

这就分成了两种顺序
左子树的顺序：左中右
右子树的顺序：右中左

有了中序遍历非递归的思想（模板）
对称改动，两两检查

这里我们先迭代到最低层
左右对比
再检查左的右，右的左，加到对应的栈顶中
每次访问完，弹栈，到上一层，递归看待问题

非递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root)return true;
        stack<TreeNode*> lstk,rstk;
        TreeNode *l = root->left,*r = root->right;
        while(l || lstk.size() || rstk.size() || r)
        { 
            while(l && r)
            {
                lstk.push(l);l = l->left;
                rstk.push(r);r = r->right;
            }
            if(l || r)return false; //只有左或只有右
            l = lstk.top(),lstk.pop();
            r = rstk.top(),rstk.pop();
            if(l->val != r->val)return false;
            l = l->right,r = r->left;
        }
        return true;
    }
};

递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root)return true;
        return dfs(root->left,root->right);
    }
    bool dfs(TreeNode* left,TreeNode *right)
    {
        if(!left || !right)return !left && !right;

        return left->val == right->val && dfs(left->left,right->right) && dfs(left->right,right->left);
    }
};