Leetcode # 107. Binary Tree Level Order Traversal II

Question

Problem

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

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[15,7],[9,20],[3]]
Example 2:

Input: root = [1]
Output: [[1]]
Example 3:

Input: root = []
Output: []

Constraints:

.The number of nodes in the tree is in the range [0, 2000].
.-1000 <= Node.val <= 1000

Discussion

Using a recursive function that returns a hashmap, a hashmap of the entire tree from top to bottom was obtained and a list was built. This list was reversed and returned.

Solution

Java

class Solution {
     public HashMap<Integer,List<Integer>> getRestOfTree(int level,TreeNode t){
     int value= t.val;
     List<Integer> root= new ArrayList<>();
     root.add(value);
     HashMap<Integer,List<Integer>> tree= new HashMap<>();
     tree.put(level,root);
     if(t.left ==null && t.right== null){
       return tree;
     }else{
      int nextlevel =level+1;
      if(t.left==null){
         HashMap<Integer,List<Integer>> rightSubtree= getRestOfTree(nextlevel,t.right);
         tree.putAll(rightSubtree);
         return tree;
      }else if(t.right==null){
          HashMap<Integer,List<Integer>> leftSubtree= getRestOfTree(nextlevel,t.left);
         tree.putAll(leftSubtree);
         return tree;
      }else{
         HashMap<Integer,List<Integer>> leftSubtree= getRestOfTree(nextlevel, t.left);
         HashMap<Integer,List<Integer>> rightSubtree= getRestOfTree(nextlevel, t.right);
         HashMap<Integer,List<Integer>> restSubtree = new HashMap<>();
         for(Integer key:leftSubtree.keySet()){
           if(rightSubtree.containsKey(key)){
             List<Integer> rightSubtreeList = rightSubtree.get(key);
             List<Integer> leftSubtreeList= leftSubtree.get(key);
             leftSubtreeList.addAll(rightSubtreeList);
             leftSubtree.replace(key,leftSubtreeList);
           }
         }
         for(Integer key:rightSubtree.keySet()){
            if(!leftSubtree.containsKey(key)){
               List<Integer> rightSubtreeList= rightSubtree.get(key);
               restSubtree.put(key,rightSubtreeList);
            }
         }
         tree.putAll(leftSubtree);
         tree.putAll(restSubtree);
         return tree;
      }
      }
   }
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if(root==null)return new ArrayList<>();
        HashMap<Integer,List<Integer>> tree = getRestOfTree(1,root);
        List<List<Integer>> values= new ArrayList<>();
        for(Integer key: tree.keySet()){
         List<Integer> nodes= tree.get(key);
         values.add(nodes);
        }
        Collections.reverse(values);
        return values;
    }
}