欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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几乎没有什么区别,要遍历树,使用深度优先遍历树

情况:

  1. 递归结束条件:当两棵树同时遍历结束——>结点同时为空——>左右指针同时为空
  2. 如果一个结点为空,一个结点不为空,两棵树肯定不对称了
  3. 可以看作是以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);
    }
};

我学会了

我个人感觉递归真的真的不要去较真,只要你能判断这个题是重复子任务,能找到结束条件。那就按照递归的模板把结束条件和递归方式写出来就行了!