LeetCode103—Binary Tree Zigzag Level Order Traversal

你的名字 2022-07-29 09:12 11阅读 0赞

# LeetCode103—Binary Tree Zigzag Level Order Traversal #

二叉树的层序遍历变种。

--------------------

## 原题 ##

> Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).
> 
> For example:  
> Given binary tree \{3,9,20,\#,\#,15,7\},  
> 　　　　3  
> 　　　/　　\\  
> 　　9　　　　20  
> 　　　　　　/　　\\  
> 　　　　　15　　　7  
> return its zigzag level order traversal as:  
> \[  
> \[3\],  
> \[20,9\],  
> \[15,7\]  
> \]

--------------------

## 分析 ##

层序遍历的一种，不同的是，要求走的是Z字形，即第一层从左到右，第二层从右到左，依次类推，**二叉树的奇数层都是从左往右，偶数层都是从右往左**，根据此记录当前层数，如果奇数层就**`push_back(key)`**，偶数层就**`insert(v.begin(),key)`**。

--------------------

## 代码 ##

class Solution {
    private:
        void helper(vector<vector<int>>&result, TreeNode*root)
        {
            if (root == NULL)
                return;
            int front=0;
            int rear=1;
            int level = 1;
            vector<TreeNode*>q;
            vector<int>temp;
            q.push_back(root);
            while (front < q.size())
            {
                rear = q.size();
                while (front < rear)//当前层
                {
                    if ( level % 2 == 1)
                    {
                        temp.push_back(q[front]->val);
                    }
                    else if (level %2 ==0)
                    {
                        temp.insert(temp.begin(), q[front]->val);
                    }
                    if (q[front]->left != NULL)
                        q.push_back(q[front]->left);
                    if (q[front]->right != NULL)
                        q.push_back(q[front]->right);
                    ++front;
                }
                ++level;
                result.push_back(temp);
                temp.clear();
            }
        }
    public:
        vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
            vector<vector<int>>result;
            helper(result, root);
            return result;
        }
    };