107|107 Binary Tree Level Order Traversal II 107BinaryTreeLevelOrderTraversalII

【107|107 Binary Tree Level Order Traversal II】title: Binary Tree Level Order Traversal II
tags:
- binary-tree-level-order-traversal-ii
- No.107
- simple
- tree
- breadth-first-search
- queue
Description 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 / \ 920 /\ 157

return its bottom-up level order traversal as:

[ [15,7], [9,20], [3] ]

Corner Cases

empty root

Solutions Queue
Insert in head for the returned list. Use number counter to divide the layers. It's obvious that the running time is O(V) when the queue operations are all in O(1).

/** * Definition for a binary tree node. * public class TreeNode { *int val; *TreeNode left; *TreeNode right; *TreeNode(int x) { val = x; } * } */ class Solution { public List> levelOrderBottom(TreeNode root) { Queueque= new LinkedList(); List> llst = new LinkedList>(); if (root == null) {return llst; } que.offer(root); int curr = 0; int nlay = 1; while (!que.isEmpty()) { nlay = que.size(); curr = 0; List a = new LinkedList(); while(curr < nlay) { TreeNode x = que.poll(); if (x.left!= null) {que.offer(x.left); } if (x.right != null) {que.offer(x.right); } a.add(x.val); curr = curr + 1; } llst.add(0, a); } return llst; } }