####1、题目名称 101. Symmetric Tree ####2、题目内容

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

翻译： 给定一颗二叉树，检查它是否与自己的镜像是同一棵树（围绕根节点对称）

---

####3、解题思路 1

观察规律 从最简单开始别怕麻烦 从1个节点到 三层end什么样的情况符合条件    1 如果2个节点都不存在    2 如果2个节点存在一个 （跟节点值没有关系）    	3 如果2个节点都存在并且内容相等为对称什么样的情况不符合条件

判断一个root是否对称 步骤 1 如果root节点的左右两个节点 p1= root->left p2=root-rgiht 都存在 并且数组相等

步骤 2 满足条件 1 判断P1 和p2 这2个节点是满足对称条件 p3=P1->left 和p4=p2-right p5=p1-right 和p6=p2 -left

步骤 3 满足条件 2 判断 p3 和p4,p5和p6这2个节点是是否对称 重复步骤 1和2

class Solution { public:

bool check(TreeNode *leftNode, TreeNode *rightNode)    {            //01 判断2个节点是否对称        //2个节点都为空        if (leftNode == NULL && rightNode == NULL)        {                return true;        }        //2个节点不对称--结构不对称        if (leftNode == NULL || rightNode == NULL)        {                return false;        }        //2个节点不对称--内容不相等        if(leftNode->val != rightNode->val)        {            return false;        }        //02 左右节点的之树也是对称的        return  check(leftNode->left, rightNode->right) &&                 check(leftNode->right, rightNode->left);    }/*************************************************Function: 101. Symmetric TreeDescription:    // 函数功能、性能等的描述Input:          // 输入参数说明，包括每个参数的作              // 用、取值说明及参数间关系。Output:         // 对输出参数的说明。Return:         // 函数返回值的说明Others:     troy 2016.4.7*************************************************/bool isSymmetric(TreeNode* root) {    if (root == NULL)    {          return true;    }            return check(root->left, root->right);}

};

####4、解题思路 2

自己大脑是如何思考的 上面case注意

1 /

2 2 / \ / 3 4 4 3

第一次对比： 2和2 节点 符合条件 第二次对比：3和3节点 符合条件 第三次对比：4和4节点 符合条件

第四次对比：NULl NULL 符合条件 第五次对比：NULl NULL 符合条件

问题来了 轨迹 2 2 3 4 4 3 好像跟树的层次遍历顺序类似 仔细对比一下 正确顺序应该是 1 2 2 3 4 4 3 节点3和4 有通过根节点 不是 3 和3 属于不相同的节点 一个队列是解决不了这问题的就用2个队列

两个队列的出队顺序 root节点左队列A： 2 3 4 NULL NULL root节点右队列 B ：2 3 4 NULL NULL

1 /

2 2 \ 3 3

第一次对比： 2和2 节点 符合条件 第二次对比：3和 Null节点 不对称 退出

注意：如果节点是NUL也需要记录下来 ，就是这么死板 人一眼看出来，电脑记录不下来

1 节点左队列 A： 2 NULL

1 节点右队列 B ：2 3

实现步骤： 步骤 1 构造两个队列 leftQ，rightQ 分别表示左子树遍历顺序 右子树遍历顺序 步骤 2 按照层次遍历 方法 如果2个队列都不为空 然后比较front 连个节点 什么样的情况不符合条件 结构和内容都不对称 步骤 3 重复步骤2 直到结束，如果方向2个队列还有剩余为false

/************************************************* Function: 101. Symmetric Tree Description: 是否对称 Input: root Output:

Return: true --对称 false--不对称 Others: troy 2016.4.7 *************************************************/ bool isSymmetric2(TreeNode *root) { //如果root为null 直接返回 if(root==NULL) { return true; }

queue
    
      leftQ;//leftQ  保存左子树遍历顺序queue
     
       rightQ;//rightQ 保存右子树遍历顺序leftQ.push(root->left); rightQ.push(root->right);       TreeNode* l;TreeNode* r;while(!leftQ.empty() && !rightQ.empty()){    l = leftQ.front();    leftQ.pop();    r = rightQ.front();    rightQ.pop();        if(l == NULL && r == NULL) continue;//上面算法如果NULL 返回true 为叶子结点 继续遍历    if(l == NULL || r == NULL) return false;//结构不对称    if(l->val != r->val) return false;//数值不对称      //注意如队列顺序 观察出来的 3=3  4 =4     leftQ.push(l->left);//左 3 右 4    leftQ.push(l->right);    rightQ.push(r->right);//右 3 左4     rightQ.push(r->left);}//如果还有剩余说明不结构不对称 例如 root只有一个if(!leftQ.empty() || !rightQ.empty()){    return false;} return true;
     
    

} ####5、解题思路 3

• [x] 一颗tree 我按照一定顺序遍历完毕，然后观察规律 这个方法不可取 因为存储结构是二叉树 不是数组即使有规律NULL无法完成保存下来 不可以

• [x] 一颗tree是对称树 那么左右子树遍历顺序结果是一样的

  1 /

  2 2 / \ /
  3 4 4 3

1 左节点中须遍历顺序 3 2 4 1 右节点中队列 B ： 2 4 3 不可以

1 左节点后须遍历顺序 3 4 3

1 右节点后须遍历顺序 ： 3 4 2 不可以

1 左节点中须遍历顺序 3 4 2

1 右节点后须遍历顺序 ： 3 4 2 可以

缺点：必须完全遍历完毕才可以知道 遍历过程中无法比较

####6、 测试用例

Your input [1,2,2,#,#,3] Your answer false Expected answer false Runtime: 0 ms

####7、 总结 如果没有推理 ，记住结论 情况一边就仍然不会 难点： 假如i,j2个节点 判断是否对称很容易 内容一样 如果摆脱tree这么多层次位置，集中到2个节点上进行比较 手工去演示过程 最直接解题思路 必须要完整去演示过程 如果演示不过 说明思路有问题。 遇到问题：

• [ ] book 上说遍历（先，中，后） 都是参数都是一个节点，现在变成2个节点了 不知道该如何办了 对称 肯定是2个节点进行比较

• [ ] 还有是遍历都（递归方式 还是非递归）记录上下节点位置（父子） 左右节点位置不好记录 （孩子之间）

类似题目： 104. Maximum Depth of Binary Tree Next challenges: (M) Convert Sorted List to Binary Search Tree

(M) Graph Valid Tree (E) Closest Binary Search Tree Value