LeetCode101——对称二叉树——c++版本实现
程序员文章站
2022-05-20 13:49:43
...
题面来啦~
给定一个二叉树,检查它是否是镜像对称的。
例如,二叉树
[1,2,2,3,4,4,3]
是对称的。1 / \ 2 2 / \ / \ 3 4 4 3
但是下面这个
[1,2,2,null,3,null,3]
则不是镜像对称的: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) {
}
};
如果还没有看我的前一篇Leetcode100的朋友请先去看那篇哦~ 强烈建议先100后101,101这道题可以有效检验你是否学会了如100这种二叉树的递归操作思想!
如果看过了100的话,我们就开始讲解啦~
其实思路很简单,根据镜像的定义,不过是在遍历的时候设置两个指针,一个向左一个向右同时遍历,并逐步比对。
但我们发现这道题的函数只有根节点,那带一个双参的子函数就可以完美解决啦~ 下面给出代码哦
要注意的是,根节点的子节点情况我选择在原始函数中给出判断,这样方便子函数安安心心的往下遍历~
class Solution {
public:
bool search(TreeNode* r1,TreeNode* r2)
{
if(r1&&r2)
return r1->val==r2->val&&search(r1->left,r2->right)&&search(r1->right,r2->left);
else if((r1&&!r2)||(!r1&&r2))
return false;
else return true;
}
bool isSymmetric(TreeNode* root) {
if(!root)
return true;
if(!root->left&&!root->right)
return true;
return search(root->left,root->right);
}
};
下面给大家带来迭代的方法,下面的方法分别是基础的队列、栈的应用~ 原理很简单,上机熟悉就好
首先是queue 队列的方法,主要的函数为 front() empty() pop() push()
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if(!root)
return true;
//左树
TreeNode *p1 = root;
//右树
TreeNode *p2 = root;
if(!p1->left&&!p1->right)
return true;
queue<TreeNode *> left,right;
left.push(p1->left);
right.push(p2->right);
while(!left.empty()&&!right.empty())
{
p1 = left.front();
left.pop();
p2 = right.front();
right.pop();
if(!p1&&!p2)
continue;
else if(!p1||!p2)
return false;
else if(p1->val!=p2->val)
return false;
left.push(p1->left);
left.push(p1->right);
right.push(p2->right);
right.push(p2->left);
}
return true;
}
};