/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    //先序遍历的顺序分为两种先左后右和先右后左两种顺序遍历，如果两者相等说明二叉树是对称的二叉树
    bool recursion(TreeNode* pRoot1,TreeNode* pRoot2)
    {
        //两个都为空,说明初始都为空或者比较到了叶子结点的下一结点，前面
        //所有的结点都相等，说明是对称的
        if(!pRoot1 && !pRoot2)
            return true;
        //只有一个为空或者节点值不同，必定不对称
        if(!pRoot1 || !pRoot2 || pRoot1->val != pRoot2->val)
            return false;
        //继续递归比较左右子树，返回相与的结果，如果有一边不对称则不对称
        return recursion(pRoot1->left, pRoot2->right) && recursion(pRoot1->right, pRoot2->left);
    }
    bool isSymmetrical(TreeNode* pRoot) 
    {
        return recursion(pRoot, pRoot);
    }

};

依据前序遍历进行递归

  • 终止条件： 当进入子问题的两个节点都为空，说明都到了叶子节点，且是同步的，因此结束本次子问题，返回true；当进入子问题的两个节点只有一个为空，或是元素值不相等，说明这里的对称不匹配，同样结束本次子问题，返回false。
  • 返回值： 每一级将子问题是否匹配的结果往上传递。
  • 本级任务： 每个子问题，需要按照上述思路，“根左右”走左边的时候“根右左”走右边，“根左右”走右边的时候“根右左”走左边，一起进入子问题，需要两边都是匹配才能对称。

具体做法：

  • step 1：两种方向的前序遍历，同步过程中的当前两个节点，同为空，属于对称的范畴。
  • step 2：当前两个节点只有一个为空或者节点值不相等，已经不是对称的二叉树了。
  • step 3：第一个节点的左子树与第二个节点的右子树同步递归对比，第一个节点的右子树与第二个节点的左子树同步递归比较。