面试题28

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

例如，二叉树 [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

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

限制：

• 0 <= 节点个数 <= 1000

注意：本题与主站 101 题相同：https://leetcode-cn.com/problems/symmetric-tree/

Solutions

• See problem 101 for more solutions.

• recursion(preorder)

/**
 * 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 same(TreeNode * l, TreeNode * r) {
        if (l && r) {
            return l->val == r->val 
            && same(l->left, r->right) 
            && same(l->right, r->left);
        }
        else return !l && !r;
    }
    bool isSymmetric(TreeNode* root) {
        return !root || same(root->left, root->right);
    }
};

1. levelorder traversal with queue

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (!root) return true;
        queue<TreeNode *> q1;
        queue<TreeNode *> q2;
        q1.push(root->left);
        q2.push(root->right);

        TreeNode * r1, * r2;

        while (!q1.empty() && !q2.empty()) {
            r1 = q1.front(); q1.pop();
            r2 = q2.front(); q2.pop();
            if (!r1 && !r2) continue;
            if ((!r1 || !r2) || r1->val != r2->val)
                return false;
            q1.push(r1->left);
            q1.push(r1->right);
            q2.push(r2->right);
            q2.push(r2->left);
        }

        return q1.empty() && q2.empty();
    }
};

1. preorder/inorder traversal with stack

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (!root) return true;
        stack<TreeNode *> s1;
        stack<TreeNode *> s2;
        TreeNode * r1 = root->left;
        TreeNode * r2 = root->right;

        while (r1 || r2 || !s1.empty() || !s2.empty()) {
            if (r1 && r2 && s1.size() == s2.size()) {
                if (r1->val != r2->val)
                    return false;
                if (r1->right)
                    s1.push(r1->right);
                if (r2->left)
                    s2.push(r2->left);
                r1 = r1->left;
                r2 = r2->right;
            }
            else if (!r1 && !r2) {
                r1 = s1.top(); s1.pop();
                r2 = s2.top(); s2.pop();
            }
            else
                return false;
        }

        return true;
    }
};