[数据结构与算法]LeetCode 对称二叉树

递归三步曲：

1. 确定参数和返回值
   因为要比较的是根节点的两个子树是否是相互翻转的，所以要比较的是两个树，参数自然就是左子树结点和右子树结点
   bool compare(TreeNode* left, TreeNode* right)
2. 递归终止条件
   （1）有点为空 （2）结点都不为空则比较两者是否相等

if (left == NULL && right != NULL) return false;
else if (left != NULL && right == NULL) return false;
else if (left == NULL && right == NULL) return true;
else if (left->val != right->val) return false; // 注意这里我没有使用else

3. 确定单层递归的逻辑
   此时才进入单层递归的逻辑，单层递归的逻辑就是处理 右节点都不为空，且数值相同的情况。
   （1）比较二叉树外侧是否对称：传入的是左节点的左孩子，右节点的右孩子。
   （2）比较内测是否对称，传入左节点的右孩子，右节点的左孩子。
   （3）如果左右都对称就返回true ，有一侧不对称就返回false 。

bool outside = compare(left->left, right->right);   // 左子树：左、 右子树：右
bool inside = compare(left->right, right->left);    // 左子树：右、 右子树：左
bool isSame = outside && inside;                    // 左子树：中、 右子树：中（逻辑处理）
return isSame;

如上代码中，我们可以看出使用的遍历方式，左子树左右中，右子树右左中，所以我把这个遍历顺序也称之为“后序遍历”（尽管不是严格的后序遍历）。