[LeetCode] Symmetric Tree
1、题目名称
- Symmetric Tree https://leetcode.com/problems/symmetric-tree/
2、题目内容
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:
1
/ \
2 2
/ \ / \
3 4 4 3But the following is not:
1
/ \
2 2
\ \
3 3翻译： 给定一颗二叉树，检查它是否与自己的镜像是同一棵树（围绕根节点对称）
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<TreeNode*> leftQ;//leftQ 保存左子树遍历顺序queue<TreeNode*> 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
一颗tree 我按照一定顺序遍历完毕，然后观察规律 这个方法不可取 因为存储结构是二叉树 不是数组即使有规律NULL无法完成保存下来 不可以
一颗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个节点进行比较 还有是遍历都（递归方式 还是非递归）记录上下节点位置（父子） 左右节点位置不好记录 （孩子之间）
类似题目：
- 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