题解 | #对称的二叉树#

#include<stack>
#include <vector>
class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot) {
	    // 特殊情况
        if (!pRoot) {
            return true;
        }

        if (!pRoot->left && !pRoot->right) return true;

        if (!pRoot->left || !pRoot->right) return false;

        if (!pRoot->left->val || !pRoot->right->val) return false;
		// 一般情况
        auto whole_stack = new stack<TreeNode*>();
        auto currentLevel = new vector<TreeNode*>();
        currentLevel->push_back(pRoot);

        while(!currentLevel->empty())
        {
            auto nextLevel= new vector<TreeNode*>();

            for (auto it = currentLevel->begin(); it != currentLevel->end(); ++it){
                auto left = (*it)-> left;

                if (whole_stack->empty()){
                    whole_stack->push(left);
                } else if (whole_stack->top() == left){
                    whole_stack->pop();
                } else if (!whole_stack->top() || !left){
                    whole_stack->push(left);
                } else if (whole_stack->top()->val ==  left->val){
                    whole_stack->pop();
                } else {
                    whole_stack->push(left);
                }

                auto right = (*it)-> right;

                if (whole_stack->empty()){
                    whole_stack->push(right);
                } else if (whole_stack->top() == right){
                    whole_stack->pop();
                } else if (!whole_stack->top() || !right){
                    whole_stack->push(right);
                } else if (whole_stack->top()->val ==  right->val){
                    whole_stack->pop();
                } else {
                    whole_stack->push(right);
                }

                if (left) {
                    nextLevel->push_back(left);
                }

                if (right) {
                    nextLevel->push_back(right);
                }
            }

            if (!whole_stack->empty()) return false;

            currentLevel = nextLevel;
        }
        return true;
    }
};

1. 层次遍历
2. 使用栈记录每一层的对称情况