107. Binary Tree Level Order Traversal II
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).
Constraints
Approach
Links
YouTube
Examples
Input: [3, 9, 20, null, null, 15, 7]
Output:
[
[15, 7],
[9, 20],
[3]
]
Solutions
// 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;
}
}/**
* Time complexity : O(N) since each node is processed exactly once.
* Space complexity : O(N) to keep the output structure which contains N
* node values.
*/
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> resultList = new ArrayList();
if(root != null) {
levelOrderBottom(resultList, root, 0);
Collections.reverse(resultList);
}
return resultList;
}
private void levelOrderBottom(List<List<Integer>> resultList,
TreeNode node,
int level) {
if(resultList.size() == level) {
resultList.add(new ArrayList<Integer>());
}
resultList.get(level).add(node.val);
if(node.left != null) {
levelOrderBottom(resultList, node.left, level+1);
}
if(node.right != null) {
levelOrderBottom(resultList, node.right, level+1);
}
}
}Follow up
Previous106. Construct Binary Tree from Inorder and Postorder TraversalNext108. Convert Sorted Array to Binary Search Tree
Last updated
Was this helpful?