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;
}
}
SOCIAL SHARE CARD GENERATOR