判断二叉树是否对成

两种方法：

• 递归法——左子树与右子树比较、右子树与左子树比较（3ms + 504KB）
• 迭代法——借助两个栈实现(3ms + 376KB)

递归

//
// Created by jt on 2020/8/22.
//
using namespace std;


class Solution {
public:
    /**
     *
     * @param root TreeNode类
     * @return bool布尔型
     */
    bool isSymmetric(TreeNode *root) {
        // write code here
        if (!root) return true;
        return isChildSymmetric(root->left, root->right);
    }

    bool isChildSymmetric(TreeNode *left, TreeNode *right) {
        // 中左右 中右左
        if (!left && !right) return true;
        if (left == nullptr ^ right == nullptr) return false;
        if (left->val != right->val) return false;

        return isChildSymmetric(left->left, right->right) &&
               isChildSymmetric(left->right, right->left);
    }
};

迭代

//
// Created by jt on 2020/8/22.
//
#include <stack>
using namespace std;


class Solution {
public:
    /**
     *
     * @param root TreeNode类
     * @return bool布尔型
     */
    bool isSymmetric(TreeNode *root) {
        // write code here
        if (!root) return true;
        if (!root->left && !root->right) return true;
        if (root->left == nullptr ^ root->right == nullptr) return false;
        stack<TreeNode *> st1, st2;
        // 中左右 中右左
        st1.push(root->left); st2.push(root->right);
        while (!st1.empty() && !st2.empty()) {
            TreeNode *node1 = st1.top(), *node2 = st2.top();
            st1.pop(); st2.pop();
            if (node1->val != node2->val) return false;
            if (node1->left == nullptr ^ node2->right == nullptr) return false;
            if (node1->right == nullptr ^ node2->left == nullptr) return false;
            if (node1->left) st1.push(node1->left); if (node1->right) st1.push(node1->right);
            if (node2->right) st2.push(node2->right); if (node2->left) st2.push(node2->left);
        }
        if (st1.empty() && st2.empty()) return true;
        return false;
    }
};