博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【LeetCode】101. Symmetric Tree (2 solutions)
阅读量:5879 次
发布时间:2019-06-19

本文共 2763 字,大约阅读时间需要 9 分钟。

Symmetric Tree

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.

 

不管是递归还是非递归,找到关系就好做。

所谓对称,也就是:

1、left对应right

2、left->left对应right->right

3、left->right对应right->left

 

解法一:递归

/** * Definition for binary tree * 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 isSymTree(root->left, root->right);    }    bool isSymTree(TreeNode* p, TreeNode* q)    {        if(!isSameNode(p, q))            return false;        if(!p && !q)            return true;        return isSymTree(p->left, q->right) && isSymTree(p->right, q->left);    }    bool isSameNode(TreeNode* p, TreeNode* q)    {        if(!p && !q)            return true;        if((!p && q) || (p && !q) || (p->val != q->val))            return false;        return true;    }};

 

解法二:非递归

使用两个队列,对左右子树分别进行层次遍历。

进队时的对应元素比较即可。

/** * Definition for binary tree * 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;                    if(!isSameNode(root->left, root->right))            return false;        if(!root->left && !root->right)            return true;                    queue
lqueue; queue
rqueue; lqueue.push(root->left); rqueue.push(root->right); while(!lqueue.empty() && !rqueue.empty()) { TreeNode* lfront = lqueue.front(); TreeNode* rfront = rqueue.front(); lqueue.pop(); rqueue.pop(); if(!isSameNode(lfront->left, rfront->right)) return false; if(lfront->left && rfront->right) { lqueue.push(lfront->left); rqueue.push(rfront->right); } if(!isSameNode(lfront->right, rfront->left)) return false; if(lfront->right && rfront->left) { lqueue.push(lfront->right); rqueue.push(rfront->left); } } return true; } bool isSameNode(TreeNode* p, TreeNode* q) { if(!p && !q) return true; if((!p && q) || (p && !q) || (p->val != q->val)) return false; return true; }};

转载地址:http://zbdix.baihongyu.com/

你可能感兴趣的文章
C#------连接SQLServer和MySQL字符串
查看>>
Arcgis Licensemanager 不能启动的原因之一(转载)
查看>>
(原)Android在子线程用handler发送的消息,主线程是怎么loop到的?
查看>>
$digest already in progress 解决办法——续
查看>>
虚拟机 centos设置代理上网
查看>>
Struts2中Date日期转换的问题
查看>>
mysql 数据类型
查看>>
Ubuntu 设置当前用户sudo免密码
查看>>
设置tomcat远程debug
查看>>
android 电池(一):锂电池基本原理篇【转】
查看>>
Total Command 常用快捷键
查看>>
ionic 调用手机的打电话功能
查看>>
怎么使用阿里云直播服务应用到现在主流直播平台中
查看>>
Xcode全局替换内容,一键Replace
查看>>
1000 加密算法
查看>>
exif_imagetype() 函数在linux下的php中不存在
查看>>
Ruby的case语句
查看>>
Linux的链接文件-ln命令
查看>>
maven的tomcat插件如何进行debug调试
查看>>
table表头固定
查看>>