leetcode 103. Binary Tree Zigzag Level Order Traversal BFS广度优先遍历

雨点打透心脏的1/2处 2022-06-08 03:15 120阅读 0赞

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,null,null,15,7\],  
3  
/ \\  
9 20  
/ \\  
15 7  
return its zigzag level order traversal as:  
\[  
\[3\],  
\[20,9\],  
\[15,7\]  
\]

题意很简单，和上一道题一样是一个BFS广度优先搜索。

代码如下：

import java.util.ArrayList;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Queue;
    
    /*class TreeNode 
    {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    */
    public class Solution
    {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root)
        {
            List<List<Integer>> res=new ArrayList<>();
            if(root==null)
                return res;
    
            Queue<TreeNode> myQueue=new LinkedList<TreeNode>();
            myQueue.add(root);  
            //flag控制方向，0表示从左到右的遍历，1表示从右到左的遍历
            int flag=0;
            while(myQueue.isEmpty()==false)
            {
                List<Integer> one=new ArrayList<>(); 
                int size=myQueue.size();
                for(int i=0;i<size;i++)
                {
                    TreeNode tmp=myQueue.peek();
                    if(tmp!=null)
                    {
                        myQueue.add(tmp.left);
                        myQueue.add(tmp.right);
    
                        if(flag==0)
                            one.add(tmp.val);
                        else
                            one.add(0, tmp.val);
                    }
                    myQueue.poll();
                }
                if(one.size()>=1)
                    res.add(one);
                flag=(flag+1)%2;
            }
            return res;
        }
    }

下面是C++的做法，和上一道题做法一模一样，就是一个BFS广度优先遍历的做法，

代码如下：

#include <iostream>
    #include <vector>
    #include <algorithm>
    #include <queue>
    
    using namespace std;
    
    /*
    struct TreeNode
    {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    */
    
    class Solution 
    {
    public:
        vector<vector<int>> zigzagLevelOrder(TreeNode* root)
        {
            vector<vector<int>> res;
            if (root == NULL)
                return res;
            queue<TreeNode*> que;
            que.push(root);
            bool flag = true;
            while (que.empty() == false)
            {
                int size = que.size();
                vector<int> one;
                for (int i = 0; i < size; i++)
                {
                    TreeNode* top = que.front();
                    que.pop();
                    one.push_back(top->val);
                    if (top->left != NULL)
                        que.push(top->left);
                    if (top->right != NULL)
                        que.push(top->right);
                }
                if(flag==false)
                    reverse(one.begin(),one.end());
                res.push_back(one);
                flag = !flag;
            }
            return res;
        }
    };