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

╰半夏微凉° 2022-06-08 02:14 165阅读 0赞

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

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

这道题很简单，就是一个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; }
     }*/
    
    /*
     * 简单的BFS广度优先遍历
     * */
    public class Solution 
    {
        public List<List<Integer>> levelOrderBottom(TreeNode root)
        {
            List<List<Integer>> res=new ArrayList<List<Integer>>();
            if(root==null)
                return res;
    
            Queue<TreeNode> myQueue=new LinkedList<TreeNode>();
            myQueue.add(root);
            while(myQueue.isEmpty()==false)
            {
                int size=myQueue.size();
                List<Integer> tmp=new ArrayList<>();
                for(int i=0;i<size;i++)
                {
                    TreeNode one=myQueue.poll();
                    tmp.add(one.val);
                    if(one.left!=null)
                        myQueue.add(one.left);
                    if(one.right!=null)
                        myQueue.add(one.right);
                }
                if(res.size()<=0)
                    res.add(tmp);
                else
                    res.add(0, tmp);    
            }
            return res;
        }
    }

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

代码如下：

#include <iostream>
    #include <vector>
    #include <queue>
    #include <algorithm>
    
    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>> levelOrderBottom(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);
            }
            reverse(res.begin(),res.end());
            return res;
        }
    };