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).
For example:
Given binary tree [7,2,1,null,null,8,23],
7
/ \
2 9
/ \
8 23
Return it’s bottom-up order traversal:
[ [7,2], [9,8], [23]]
Solution:
In this type of traversal, we have to go from bottom to up. We always traverse any tree from top to bottom, but in this case we have to return just reverse of the usual traversal.
So, we can traverse through the tree from top to bottom and reverse our traversa at the end.
In this implementation, we need a list(in java) or array to solve it efficiently.
Algorithm:
We use a recursive function to stepwise solve this problem. In this approach we traverse the tree step by step from top to bottom untill we reach to null in both the left subtree and right subtree. We simply add the current node we have into the temporary list and just after that we add this node to the required ans list at index 0 everytime. This will add the node in reverse order which is our required answer. We call this recursion with left node and right node of the current scenerio again and again untill we reach to the null value at both the ends.
Implementation:
Java:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private List<List<Integer>> ans = new ArrayList<>();
private void dfs(TreeNode node, int depth){
if(node==null){ return ; }
if(ans.size() > depth){ ans.get(ans.size()-1-depth).add(node.val); }
else{
List<Integer> temp = new ArrayList<>();
temp.add(node.val);
ans.add(0, temp);
}
dfs(node.left, depth+1);
dfs(node.right, depth+1);
}
public List<List<Integer>> levelOrderBottom(TreeNode root) {
dfs(root, 0);
return ans;
}
}
Complexity Analysis:
- Time Complexity: O(n).
- Space Complexity: O(n).
