LeetCode101(力扣101):对称二叉树 C++
程序员文章站
2022-05-20 13:53:08
...
101.对称二叉树
给定一个二叉树,检查它是否是镜像对称的。
例如,二叉树 [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
进阶:
你可以运用递归和迭代两种方法解决这个问题吗?
我提交的代码
class Solution {
public:
bool isDCtree(TreeNode* p, TreeNode* q) {
if (p == nullptr) return q == nullptr;
return (q != nullptr) && (p->val == q->val) && isDCtree(p->left, q->right) && isDCtree(p->right, q->left);
}
bool isSymmetric(TreeNode* root) {
return isDCtree(root, root);
}
};
此题还可以用if else语句来写,详情可以见100题解,这里就不重复了。
我的思想
这个题和第100几乎没有什么区别,要遍历树,使用深度优先遍历树
情况:
- 递归结束条件:当两棵树同时遍历结束——>结点同时为空——>左右指针同时为空
- 如果一个结点为空,一个结点不为空,两棵树肯定不对称了
- 可以看作是以root的左树和右树作为两颗树,左树的左孩子=右树的右孩子,左树的右孩子=右树的左孩子,两个条件同时满足进行递归。
官方题解
class Solution {
public:
bool check(TreeNode *p, TreeNode *q) {
if (!p && !q) return true;
if (!p || !q) return false;
return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);
}
bool isSymmetric(TreeNode* root) {
return check(root, root);
}
};
我学会了
我个人感觉递归真的真的不要去较真,只要你能判断这个题是重复子任务,能找到结束条件。那就按照递归的模板把结束条件和递归方式写出来就行了!
上一篇: C++Leetcode101:对称二叉树