MENU

LeetCode101. Symmetric Tree(二叉树 / 模拟)

2019 年 03 月 07 日 • 阅读: 831 • LeetCode阅读设置

LeetCode101. Symmetric Tree(二叉树 / 模拟)

  • Easy
  • Accepted:362,120
  • Submissions:847,066

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

    1
   / \
  2   2
   \   \
   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.


链接

https://leetcode.com/problems/symmetric-tree

题意

给定一棵二叉树,判断它是否是对称的。

题解

之前有两道题,一道是反转一棵二叉树:LeetCode226. Invert Binary Tree(二叉树 / 模拟),还有一道是判断两颗二叉树是否相同:LeetCode100. Same Tree(二叉树 / 模拟),所以一个稍麻烦的做法是先将其反转然后判断与原二叉树是否相同。

还有一种做法就是转化为比较两颗二叉树是否相同,“左右”和“右左”相比

同样的我们可以使用队列来进行“左右”和“右左”的比较,每次压入两个结点即可,这个思路实在是太巧妙了。不过注意一下当p和q为空时的判断。

代码

  • Runtime: 12 ms, faster than 97.51% of C++ online submissions for Symmetric Tree.
  • Memory Usage: 15.9 MB, less than 71.66% of C++ online submissions for Symmetric Tree.
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return isSame(root, root);
    }

private:
    bool isSame(TreeNode* p, TreeNode* q)
    {
        if (p == NULL || q == NULL)
            return (p == q);
        if (p->val != q->val)
            return false;]
        return isSame(p->left, q->right) && isSame(p->right, q->left);
    }
};
  • Runtime: 12 ms, faster than 97.51% of C++ online submissions for Symmetric Tree.
  • Memory Usage: 15.8 MB, less than 76.90% of C++ online submissions for Symmetric Tree.
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        queue <TreeNode*> q;
        q.push(root);
        q.push(root);
        while (!q.empty())
        {
            TreeNode* p1 = q.front();
            q.pop();
            TreeNode* p2 = q.front();
            q.pop();
            if (p1 == NULL && p2 == NULL)
                continue;
            if (p1 == NULL || p2 == NULL)
                    return false;
            if (p1->val != p2->val)
                return false;
            q.push(p1->left);
            q.push(p2->right);
            q.push(p1->right);
            q.push(p2->left);
        }
        return true;
    }
};

The end.
2019年3月7日 星期四
最后编辑于: 2019 年 03 月 13 日