对称二叉树

DFS

递归三步走：

1. 递归结束条件：如果左右字节点均为空，返回true
2. 找到函数等价式: 如果左右子节点其中一个为空或者左右子节点均不为空并且两个子节点的值不等，返回false(判断是否对称就是当前递归的函数等价式)
3. 递归函数返回值：左子节点的左子节点和右子节点的右子节点比较，左子节点的右子节点和右子节点的左子节点比较，当这两个比较结果都为真的时候，返回真

判断二叉树是否是对称，需要从子节点开始比较，两个子节点的值必须相同，并且左子节点的右子节点（如果有）必须等于右子节点的左子节点，左子节点的左子节点必须等于右子节点的右子节点。就像下面图中那样

 class Solution {
 public:
     bool isSymmetric(TreeNode* root) 
     {
         if (!root) return true;
         //从两个子节点开始判断
         return is(root->left, root->right);
     }
     bool is(TreeNode* left, TreeNode* right)
     {
         //如果左右子节点都为空，说明当前节点是叶子节点，返回true
         if (!left && !right) return true;
         //如果当前节点只有一个子节点或者有两个子节点，但两个子节点的值不相同，直接返回false
         if (!left || !right || left->val != right->val) return false;
         //然后左子节点的左子节点和右子节点的右子节点比较，左子节点的右子节点和右子节点的左子节点比较
         return is(left->left, right->right) && is(left->right, right->left);
     }
 };

BFS

非递归

 class Solution {
 public:
     bool isSymmetric(TreeNode* root) 
     {
         if (!root)
             return true;
         queue<TreeNode*> q;
         //左右字节点入队
         q.push(root->left);
         q.push(root->right);
         //队列不为空
         while (!q.empty())
         {
             //获取当前对头两元素
             TreeNode* left = q.front();
             q.pop();
             TreeNode* right = q.front();
             q.pop();
             //如果两个都为空，符合对称要求，直接进行下一次循环
             if (!left && !right) continue;
             //如果其中一个为空，出现不对称
             if (!left || !right) return false;
             //如果当前左右字节的值不等，出现不对称
             if (left->val != right->val) return false;
         //这里要记住入队的顺序，他会每两个两个的出队。
        //左子节点的左子节点和右子节点的右子节点同时
        //入队，因为他俩会同时比较。
        //左子节点的右子节点和右子节点的左子节点同时入队，
        //因为他俩会同时比较
             q.push(left->left);
             q.push(right->right);
             q.push(left->right);
             q.push(right->left);
         }
         return true;
     }
 };