LeetCode OJ：Symmetric Tree（对称的树）
2024-09-28 06:35:20
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
判断一颗树是否对称，首先用递归的方法当然比较容易解决：
/**
* 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 == NULL)
return true;
if(!root->left && !root->right)
return true;
if(root->left && !root->right || !root->left && root->right)
return false;
return checkSymmetric(root->left, root->right);
} bool checkSymmetric(TreeNode * left, TreeNode * right)
{
if(!left && !right)
return true;
if(!left && right || left && !right)
return false;
if(left->val != right->val)
return false;
return checkSymmetric(left->left, right->right) && checkSymmetric(left->right, right->left);
}
};
题目还要求用非递归的方式来实现，制造两个队列就可以实现了：
/**
* 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) {
queue<TreeNode *> q1;
queue<TreeNode *> q2;
if(root == NULL) return true;
if(!root->left && !root->right) return true;
if(root->left && !root->right || !root->left && root->right) return false;//val
q1.push(root->left);
q2.push(root->right);
TreeNode * tmpLeft, *tmpRight;
while(!q1.empty() && !q2.empty()){
tmpLeft = q1.front();
tmpRight = q2.front();
q1.pop(), q2.pop();
if(!tmpLeft && !tmpRight)
continue;
if(!tmpLeft && tmpRight || tmpLeft && !tmpRight)
return false;
if(tmpLeft->val != tmpRight->val)
return false;
q1.push(tmpLeft->left);
q1.push(tmpLeft->right);
q2.push(tmpRight->right);
q2.push(tmpRight->left);
}
return q1.empty() && q2.empty();
}
};
java的递归版本如下所示：
public class Solution {
public boolean isSymmetric(TreeNode root) {
if(root == null)
return true;
if(root.left == null && root.right == null)
return true;
if(root.left != null && root.right != null)
return checkSymmetric(root.left, root.right);
return false;
}
public boolean checkSymmetric(TreeNode leftNode, TreeNode rightNode){
if(leftNode == null && rightNode == null)
return true;
if(leftNode != null && rightNode != null){
if(leftNode.val == rightNode.val){
return checkSymmetric(leftNode.left, rightNode.right) &&
checkSymmetric(leftNode.right, rightNode.left);
}
else
return false;
}
return false;
}
}
下面是迭代版本，和上面的基本上一样：
public class Solution {
public boolean isSymmetric(TreeNode root) {
Queue<TreeNode> q1 = new LinkedList<TreeNode>();
Queue<TreeNode> q2 = new LinkedList<TreeNode>();
TreeNode p1, p2;
if(root == null)
return true;
q1.add(root.left);
q2.add(root.right);
while(!q1.isEmpty() && !q2.isEmpty()){
p1 = q1.poll();
p2 = q2.poll();
if(p1 == null && p2 == null)
continue;
if(p1 != null && p2 != null){
if(p1.val == p2.val){
q1.add(p1.left);
q1.add(p1.right);
q2.add(p2.right);
q2.add(p2.left);
}else
return false;
}else
return false;
}
return true;
}
}
最新文章
- BZOJ1202 [HNOI2005]狡猾的商人&&BZOJ3436小K的农场
- 1.把二元查找树转变成排序的双向链表[BST2DoubleLinkedList]
- 与众不同 windows phone (47) - 8.0 其它: 锁屏信息和锁屏背景, 电池状态, 多分辨率, 商店, 内置协议, 快速恢复
- Ubuntu/Deepin下常用软件汇总(持续更新)
- unity3d中Find的用法
- asp.net webapi 生成在线文档--Swagger
- Spark注册UDF函数，用于DataFrame DSL or SQL
- java 大数据运算 BigInteger BigDecimal
- “耐撕”团队 2016.03.25 站立会议
- PSP（4.13——4.19）以及周记录
- 实现DIV层内的文字垂直居中(转)
- 如何感性地理解EM算法？
- ADO.NET实体数据模型中关于数据库字段默认值的处理
- 币安Binance API
- 【JMeter】如何录制创建及得到曲线图
- PHP5.2 $arr = [] 初始化数组出现问题
- CSU 1425 Prime Summation
- Mybatis中select传递多个参数
- python基础===【爬虫】爬虫糗事百科首页图片代码
- 树剖模板by fcdalao