Submissions: 273390 Difficulty: Easy
给定一颗二叉树,检查是否镜像对称(环绕中心对称)
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 3
But the following is not:非对称的二叉树
1
/ \
2 2
\ \
3 3
Note:
Bonus points if you could solve it both recursively and iteratively.
confused what "{1,#,2,3}"
means? >
read more on how binary tree is serialized on OJ.
Subscribe to see which companies asked this question
分析(下面答案有极少的案例未通过。是错误答案!留作分析与纪念):
思路首先:
中序遍历二叉树。再推断遍历结果的对称性
以题目为样例:中序结果3241423。推断序列显然对称
以下那个不正确称的样例:23123,推断序列显然不正确称
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/ class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
if(root){
inorderTraversal(root->left);
result.push_back(root->val);
inorderTraversal(root->right);
}
return result;
} bool isSymmetric(TreeNode* root) {
if(root==NULL)
return true;
inorderTraversal(root);//获取中序结果
for(int i=0;i<result.size()/2;i++)//推断序列对称否
if(result[i]!=result[result.size()-1-i])
return false;
return true;
}
private:
vector<int> result;
};
经过一段时间的分析才发现:
1),对于二叉树形状太极端情况是无法分辨的,
2),那种本来不是对称二叉树可是他的遍历序列因为数字太巧合却是对称的就不行了!
举例情况1:他的中序遍历为。121,显然不正确称
1
\
2
\
1
举例情况2:他的中序遍历为,2222。可是显然不正确称
2
/ \
2 2
\
2
错误答案截止
学习别人的答案:
递归,从根节点開始,推断左节点的左子树与右节点的右子树,左节点的右子树与右节点的左子树是否相等就可以!
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isSymmetric(TreeNode *root) {
if (!root) return true;
return helper(root->left, root->right);
}
//推断节点的左右子树是否对称
bool helper(TreeNode* leftnode, TreeNode* rightnode) {
if (!leftnode && !rightnode) //左右子树均为空
return true; if (!leftnode || !rightnode) //单子树
return false; if (leftnode->val != rightnode->val) //左右子树不相等
return false;
//左节点的左子树与右节点的右子树。左节点的右子树与右节点的左子树
return helper(leftnode->left,rightnode->right) && helper(leftnode->right, rightnode->left);
}
};
学习别人的迭代:
class Solution {
public:
bool isSymmetric(TreeNode* root) {
queue<TreeNode*> queue;
if(!root)
return true;
queue.push(root->left);
queue.push(root->right);
TreeNode *leftnode,*rightnode; while(!queue.empty())
{
leftnode = queue.front();
queue.pop();
rightnode = queue.front();
queue.pop();
if (!leftnode && !rightnode) //左右子树均为空
continue;
if (!leftnode || !rightnode) //单子树
return false;
if(leftnode->val!=rightnode->val)//不相等
return false;
queue.push(leftnode->right);
queue.push(rightnode->left);
queue.push(leftnode->left);
queue.push(rightnode->right);
}
return true;
}
};
小结:
哎.....
注:本博文为EbowTang原创,兴许可能继续更新本文。假设转载,请务必复制本条信息!
原文地址:http://blog.csdn.net/ebowtang/article/details/50562771
原作者博客:http://blog.csdn.net/ebowtang
<LeetCode OJ> 101. Symmetric Tree的更多相关文章
-
[LeetCode&;Python] Problem 101. Symmetric Tree
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For e ...
-
【leetcode❤python】101. Symmetric Tree
#-*- coding: UTF-8 -*-# Definition for a binary tree node.# class TreeNode(object):# def __init_ ...
-
Leetcode 笔记 101 - Symmetric Tree
题目链接:Symmetric Tree | LeetCode OJ Given a binary tree, check whether it is a mirror of itself (ie, s ...
-
[leetcode] 101. Symmetric Tree 对称树
题目大意 #!/usr/bin/env python # coding=utf-8 # Date: 2018-08-30 """ https://leetcode.com ...
-
Leetcode之101. Symmetric Tree Easy
Leetcode 101. Symmetric Tree Easy Given a binary tree, check whether it is a mirror of itself (ie, s ...
-
leetcode 100. Same Tree、101. Symmetric Tree
100. Same Tree class Solution { public: bool isSameTree(TreeNode* p, TreeNode* q) { if(p == NULL &am ...
-
【LeetCode】101. Symmetric Tree (2 solutions)
Symmetric Tree Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its ...
-
LeetCode之“树”:Symmetric Tree &;&; Same Tree
Symmetric Tree 题目链接 题目要求: Given a binary tree, check whether it is a mirror of itself (ie, symmetric ...
-
LeetCode(1) Symmetric Tree
从简单的道题目開始刷题目: Symmetric Tree 题目:Given a binary tree, check whether it is a mirror of itself (ie, sym ...
随机推荐
-
中文分词之结巴分词~~~附使用场景+demo(net)
常用技能(更新ing):http://www.cnblogs.com/dunitian/p/4822808.html#skill 技能总纲(更新ing):http://www.cnblogs.com/ ...
-
Mac 下安装Jenkins
Mac 下安装Jenkins 开始 Jenkins是一个基于Java开发的一种持续集成工具,用于建工持续重复的工作,功能包括: 持续的软件版本发布/测试项目 监控外部调用执行的工作. 近期打算搭建自动 ...
-
如何在github中创建演示demo
在项目中创建一个新的gh-pages分支: 将你想要展示的示例demo上传到改分支,具体操作就看你自己啦,是merge其他分支的过来还是重新写代码都可以. 最后,通过http://<userna ...
-
D​e​p​l​o​y​m​e​n​t​ ​f​a​i​l​u​r​e​ ​o​n​ ​T​o​m​c​a​t​ ​6​.​x​.​ ​C​o​u​l​d​ ​n​o​t​ ​c​o​p​y​ ​a​l​l​ ​r​e​s​o​u​r​c​e​s​ ​t​o
在myeclipse总部署项目,一直有问题,提示如下的错误,经过研究在网上需求帮助,解决方案如下: Deployment failure on Tomcat 6.x. Could not copy ...
-
maven中snapshot快照库和release发布库的区别和作用
在使用maven过程中,我们在开发阶段经常性的会有很多公共库处于不稳定状态,随时需要修改并发布,可能一天就要发布一次,遇到bug时,甚至一天要发布N次.我们知道,maven的依赖管理是基于版本管理的, ...
-
Java死锁的例子
死锁 死锁是这样一种情形:多个线程同时被阻塞,它们中的一个或者全部都在等待某个资源被释放.由于线程被无限期地阻塞,因此程序不可能正常终止. 导致死锁的根源在于不适当地运用“synchronized”关 ...
-
ActiveX控件
什么是ActiveX控件:一个进程内服务器,支持多种的COM接口.(可以理解为,一个COM接口是一个纯抽象基类,你实现了它,并且它支持自注册,就是一个ActiveX控件了)可以把ActiveX控件看做 ...
-
js简版定时器
<html> <head> <meta http-equiv="Content-Type" content="text/html; char ...
-
ural 1215 Exactness of Projectile Hit
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> # ...
-
多线程操作UI界面的示例 - 更新进度条
http://blog.csdn.net/liang19890820/article/details/52186626