lintcode71. 二叉树的锯齿形层次遍历

喜欢ヅ旅行 2023-06-30 09:24 20阅读 0赞

给出一棵二叉树，返回其节点值的锯齿形层次遍历（先从左往右，下一层再从右往左，层与层之间交替进行）

样例
    样例 1:
    
    输入:{
        1,2,3}
    输出:[[1],[3,2]]
    解释:
        1
       / \
      2   3
    它将被序列化为 {
        1,2,3}
    样例 2:
    
    输入:{
        3,9,20,#,#,15,7}
    输出:[[3],[20,9],[15,7]]
    解释:
        3
       / \
      9  20
        /  \
       15   7
    它将被序列化为 {
        3,9,20,#,#,15,7}

/**
     * Definition of TreeNode:
     * class TreeNode {
     * public:
     *     int val;
     *     TreeNode *left, *right;
     *     TreeNode(int val) {
     *         this->val = val;
     *         this->left = this->right = NULL;
     *     }
     * }
     */
    
    class Solution {
        
    public:
        /**
         * @param root: A Tree
         * @return: A list of lists of integer include the zigzag level order traversal of its nodes' values.
         */
        vector<vector<int>> zigzagLevelOrder(TreeNode * root) {
        
            // write your code here
              vector<vector<int>>res;
            queue<TreeNode*>a;
            queue<TreeNode*>b;
            a.push(root);
            if(root==NULL) return res;
            vector<int> tmp={
        root->val};
            res.push_back(tmp);
            while(!a.empty()||!b.empty())
            {
        
                if(!a.empty())
                {
        
                    tmp.clear();
                    while(!a.empty())
                    {
        
                        if(a.front()->left)
                        {
        
                            b.push(a.front()->left);
                            tmp.push_back(a.front()->left->val);
                        }
                        if(a.front()->right) 
                        {
        
                            b.push(a.front()->right);
                            tmp.push_back(a.front()->right->val);
                        }
                        a.pop();
                    }
                    if(!tmp.empty())res.push_back(tmp);
                }
                if(!b.empty())
                {
        
                    tmp.clear();
                    while(!b.empty())
                    {
        
                        if(b.front()->left)
                        {
        
                            a.push(b.front()->left);
                            tmp.push_back(b.front()->left->val);
                        }
                        if(b.front()->right)
                        {
        
                            a.push(b.front()->right);
                            tmp.push_back(b.front()->right->val);
                        }
                        b.pop();
                    }
                    if(!tmp.empty())res.push_back(tmp);
                }
            }
            for (int i = 0; i < res.size(); i++) {
        
                /* code */
                if(i%2) reverse(res[i].begin(),res[i].end());
            }
            return res;
        }
    };