题解 | #对称的二叉树#

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    vector<int> vl, vr;
    bool isSymmetrical(TreeNode* pRoot) {
        stack<TreeNode*> sl, sr;
        TreeNode *pl = pRoot, *pr = pRoot;

        while (pl && pr || !sl.empty() && !sr.empty()) {
            while (pl && pr) {
                if (pl->val != pr->val) return false;
                sl.push(pl); sr.push(pr);
                pl = pl->left; pr = pr->right;
            } // traverse till null

            if (pl || pr) return false; // but one not null. false

            if (!sl.empty() && !sr.empty()) {
                pl = sl.top(); pr = sr.top();
                sl.pop(); sr.pop();

                pl = pl->right;
                pr = pr->left;
            }
        }
        
        return true;
    }

};

使用两个指针，加上二叉树的非递归遍历。然后一个按照LMR另一个照RML的顺序进行遍历。如若遇见两者一者为空而另一不是，或者遇见两者都非空却值不相等的情况，则可以判断非对称。否则就可以直言其对称。