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:

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

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日星期四