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 [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] ]
/**
* Definition for a binary tree node.
* public 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;
* }
* }
*/
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
LinkedList<List<Integer>> result = new LinkedList<List<Integer>>();
if(root==null)
return result;
Queue<TreeNode> q= new LinkedList<TreeNode>();
q.offer(root);
while(!q.isEmpty())
{
int size= q.size();
List<Integer> levelNodes= new ArrayList<Integer>();
for(int i=0; i<size; i++)
{
TreeNode node= q.poll();
levelNodes.add(node.val);
if(node.left != null)
q.offer(node.left);
if(node.right != null)
q.offer(node.right);
}
result.addFirst(levelNodes);
}
return result;
}
}Here, we are going to solve using Queue. The idea behind solving this problem is for each level, nodes we are visiting are storing in levelNodes list and adding it into result list.
1) If list in null return 0.
2) Else store LinkedList nodes to Queue.
3) If queue is not empty,
a) Remove the top element and store it in levelNodes list.
b) If left or right of node is not null, then add those elements again back into queue using offer().
c) After iteration, add levelNodes to result list using addFirst().
4) Repeat above steps until queue is empty.
NOTE:
1) addFirst() - The reason is, if we don't use this method and insert element using add() method then all level nodes are inserted in same order and not in expected format. For this, after finishing each level, if we use addFirst(),
If we are at level 2, then level 2 nodes are store at first and level 1 in order.
If we are at level 3, then level 3 nodes are store at first and level 2, level 1 in upcoming order.
2)offer() - The reason is, this method is preferable to add() method since this method does not throws an exception when the capacity of the container is full since it returns false.
Also Check it out:
Click here for April month challenges with solution and explanation
😍..Happy Coding...😍
Click Follow button to receive updates from us instantly.
Please let us know about your views in comment section.
Help Others, Please Share..!!!!
Comments
Post a Comment