Binary Tree Level Order Traversal II

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).

Example:

Input:  tree={3,9,20,null,null,15,7}
Output: order=[[15,7],[9,20],[3]]

Approach

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BinaryTreeLevelOrderTraversalII {
    public static void main(String[] args) {
        TreeNode tree = new TreeNode(3);
        tree.left = new TreeNode(9);
        tree.right = new TreeNode(20);
        tree.left.left = new TreeNode(15);
        tree.left.right = new TreeNode(7);
        List<List<Integer>> order = levelOrderBottom(tree);
        System.out.println(Arrays.asList(order));
    }

    static List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> x = new ArrayList<Integer>();
        if (root == null)
            return res;
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.add(root);
        while (!q.isEmpty()) {
            int len = q.size();
            while (len > 0) {
                len--;
                root = q.poll();
                x.add(root.val);
                if (root.left != null)
                    q.add(root.left);
                if (root.right != null)
                    q.add(root.right);
            }
            res.add(x);
            // reset
            x = new ArrayList<Integer>();
        }
        Collections.reverse(res);
        return res;
    }
}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
//struct for treenode
struct TreeNode{
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        this->data=data;
        this->left=NULL;
        this->right=NULL;
    }
};


vector<vector<int>> levelOrderBottom(TreeNode* root) 
{
        vector<vector<int>> res;
        vector<int> x;
        if(root==NULL)
               return res;
        queue<TreeNode *> q;
        q.push(root);
        while(!q.empty())
        {
            int len=q.size();
            while(len--)
            {
                root=q.front();
                x.push_back(root->data);
                q.pop();
                if(root->left)
                       q.push(root->left);
                if(root->right)
                       q.push(root->right);
            }
           res.push_back(x);
        x.clear();
        }
        reverse(res.begin(),res.end());
         return res;
}
int main()
{

    TreeNode *root=new TreeNode(3);
    root->left=new TreeNode(9);
    root->right=new TreeNode(20);
    root->right->left=new TreeNode(15);
    root->right->right=new TreeNode(7);
    vector<vector<int>> order=levelOrderBottom(root);

    cout<<"[";
    for(int i=0;i<order.size();i++)
      {
          cout<<"[";
          for(int j=0;j<order[i].size();j++)
            {
                cout<<order[i][j];
                if(j!=order[i].size()-1)
                  cout<<",";
            }
         cout<<"]";
         if(i!=order.size()-1)
           cout<<",";
      }
      return 0;

}