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

不念不忘少年蓝@ 2022-06-08 03:15 155阅读 0赞

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:  
Given binary tree \[3,9,20,null,null,15,7\],  
3  
/ \\  
9 20  
/ \\  
15 7  
return its level order traversal as:  
\[  
\[3\],  
\[9,20\],  
\[15,7\]  
\]

题意很简单，就是一个BFS广度优先遍历的求解，注意把握好每一层的size。

代码如下：

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>> levelOrder(TreeNode root)
        {
            List<List<Integer>> res=new ArrayList<>();
            if(root==null)
                return res;
    
            Queue<TreeNode> queue=new LinkedList<>();
            queue.add(root);
            while(queue.isEmpty()==false)
            {
                int size=queue.size();
                List<Integer> one=new ArrayList<>();
                for(int i=0;i<size;i++)
                {
                    TreeNode t=queue.poll();
                    one.add(t.val);
                    if(t.left!=null)
                        queue.add(t.left);
                    if(t.right!=null)
                        queue.add(t.right);
                }
                res.add(one);
            }
            return res;
        }
    }

下面是C++的做法，就是一个简单的BFS广度优先遍历的做法

代码如下：

#include<iostream>
    #include <vector>
    #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>> levelOrder(TreeNode* root) 
        {
            vector<vector<int>> res;
            if (root == NULL)
                return res;
            queue<TreeNode*> que;
            que.push(root);
            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);
                }
                res.push_back(one);
            }
            return res;
        }
    };