LeetCode #101：Symmetric Tree(对称二叉树)

题目描述

本题的思路为比较一棵二叉树的两个子树的里侧与外侧的元素是否相等。若采用递归算法，只能同时对左右子树进行后序遍历，通过两个递归函数的返回值判断两个子树的内侧节点和外侧节点是否相等（对左侧子树的遍历顺序是左右中，对右侧子树的遍历顺序是右左中）。

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root == NULL)
            return true;

        return cmp(root->left, root->right);
    }

    bool cmp(TreeNode* left, TreeNode* right) {
        if(left == NULL && right == NULL) // 左右节点都空，对称
            return true;
        else if(left == NULL && right) // 左节点为空，右节点不空，不对称
            return false;
        else if(left && right == NULL) // 左节点不空，右节点为空，不对称
            return false;
        else if(left->val != right->val) // 左右节点都不空但值不等，不对称
            return false;

        bool outside = cmp(left->left, right->right); // 递归外侧，取左->left与右->right
        bool inside = cmp(left->right, right->left); // 递归内侧，取左->right与右->left
        bool isSame = outside && inside;
        
        return isSame;
    }
};

本题当然也可以使用迭代法解决，区别就是在递归的地方把下一层的递归结点压栈（采用队列也是可以的）即可。

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root == NULL)
            return true;

        stack<TreeNode*> s;
        s.push(root->left);
        s.push(root->right);
        while(!s.empty()) {
            // 连续取出栈顶的两个元素，对应递归法中递归函数的参数
            auto r = s.top();
            s.pop();
            auto l = s.top();
            s.pop();
            if(l == NULL && r == NULL)
                continue; // 这里不能直接return，因为这只是一个分支上符合要求
            else if(l == NULL && r)
                return false;
            else if(l && r == NULL)
                return false;
            else if(l->val != r->val)
                return false;
            
            s.push(l->left);
            s.push(r->right);
            s.push(l->right);
            s.push(r->left);
        }
        return true;
    }
};