7.4 树遍历：level2 & Zigzag & *recover* B & sameT & symmeT

to do

XOR condition: if(!A != !B), ! is for boolean conversion, and careful of complier optimization, maybe

2] Binary Tree Zigzag Level Order Traversal

写的太慢了，mark重写

    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if (!root) return vector<vector<int>> {};
        vector<vector<int>> ret = {};
        vector<int> curr={};
        TreeNode dummy (-1);
        queue<TreeNode*> nodeQ;
        nodeQ.push(root);
        nodeQ.push(&dummy);
        
        bool reversed = false;
        while (!nodeQ.empty()) {
            TreeNode* n = nodeQ.front();
            nodeQ.pop();
            
            if (n==&dummy) {
                if (reversed) 
                    reverse(curr.begin(), curr.end());
                ret.push_back(curr);
                
                if (nodeQ.empty()) break;
                nodeQ.push(n);
                curr.clear();
                reversed = !reversed;
            } else {
                curr.push_back(n->val);
                if (n->left) nodeQ.push(n->left);
                if (n->right) nodeQ.push(n->right);
            }
        }
        return ret;
        
    }

4] same tree: easy

5] symmetric Tree, forward recursion is slow

    bool isSymmetric(TreeNode* root) {
        if (!root) return true;
        stack<TreeNode*> stk;
        stk.push(root->left);
        stk.push(root->right);
        
        while (!stk.empty()) {
            TreeNode* nr = stk.top();
            stk.pop();
            TreeNode* nl = stk.top();
            stk.pop();
            
            if (!nr != !nl) return false;
            if (nr) {
                if (nr->val != nl->val) return false;
                stk.push(nl->left);
                stk.push(nr->right);
                stk.push(nl->right);
                stk.push(nr->left);
            }
        }
        
        return true;
    }