101. Symmetric Tree

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

S1: recursion

注意是从中轴对称，并不要求左右子树本身对称

    bool isSymmetric(TreeNode* root) {
        if (!root) {
            return true;
        }
        return isSymHelper(root->left, root->right);
    }

    bool isSymHelper(TreeNode* node1, TreeNode* node2) {
        if (!node1) {
            return !node2;
        }
        if (!node2) {
            return !node1;
        }
        if (node1->val != node2->val) {
            return false;
        }
        else return isSymHelper(node1->left, node2->right) &&
                    isSymHelper(node1->right, node2->left);
    }

S2: iteration using stack

    bool isSymmetric(TreeNode* root) {
        if (!root) {
            return true;
        }
        stack<TreeNode*> stk;
        stk.push(NULL);
        stk.push(NULL);
        TreeNode* node1 = root->left;
        TreeNode* node2 = root->right;
        while (node1 && node2) {
            if (node1->val != node2->val) {
                return false;
            }
            if (node1->left && node2->right) {
                stk.push(node1->left);
                stk.push(node2->right);
            } else if (node1->left || node2->right) {  //只有一个为空
                return false;
            }
            if (node1->right && node2->left) {
                stk.push(node1->right);
                stk.push(node2->left);
            } else if (node1->right || node2->left) {
                return false;
            }
            node1 = stk.top();
            stk.pop();
            node2 = stk.top();
            stk.pop();
        }
        return !node1 && !node2;
    }