Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/107.html
107 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,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its bottom-up level order traversal as:
[
[15,7],
[9,20],
[3]
]
@tag-tree
Algorithm
The traversal from the bottom sequence is actually traversal from the top, but the final storage method has changed.
Code
-
import java.util.*; public class Binary_Tree_Level_Order_Traversal_II { /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<List<Integer>> levelOrderBottom(TreeNode root) { List<List<Integer>> list = new ArrayList<List<Integer>>(); if (root == null) { return list; } Queue<TreeNode> sk = new LinkedList<>(); sk.offer(root); sk.offer(null);// @note: use null as marker for end of level List<Integer> oneLevel = new ArrayList<>(); while (!sk.isEmpty()) { TreeNode current = sk.poll(); if (current == null) { List<Integer> copy = new ArrayList<>(oneLevel); list.add(0, copy); // diff of I and II: insert to head // clean after one level recorded oneLevel.clear();// @memorize: this api // @note:@memorize: if stack is now empty then DO NOT add null, or else infinite looping // sk.offer(null); // add marker if (!sk.isEmpty()) { sk.offer(null); // add marker } continue; } oneLevel.add(current.val); // @note:@memorize: since using null as marker, then must avoid adding null when children are null // sk.offer(current.left); // sk.offer(current.right); if (current.left != null) { sk.offer(current.left); } if (current.right != null) { sk.offer(current.right); } } return list; } } public class Solution_dummyNodeAsMarker { public List<List<Integer>> levelOrderBottom(TreeNode root) { LinkedList<List<Integer>> result = new LinkedList<List<Integer>>(); if(root == null) { return result; } // Array deques have no capacity restrictions, they grow as necessary Queue<TreeNode> queue = new ArrayDeque<TreeNode>(); // @note: another implementation queue.add(root); TreeNode dummy = new TreeNode(0); queue.add(dummy); List<Integer> currentLevel = new ArrayList<Integer>(); while(queue.size() > 1){ TreeNode current = queue.poll(); if (current.hashCode() != dummy.hashCode()) { // more specific with hashCode() currentLevel.add(current.val); if(current.left != null) queue.add(current.left); if(current.right != null) queue.add(current.right); } else { result.addFirst(new ArrayList<Integer>(currentLevel)); currentLevel.clear(); queue.add(dummy); } } // @note: LinkedList has API addFirst() result.addFirst(currentLevel); // or call reverse() // Collections.reverse(result); return result; } } } ############ /** * 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>> ans = new LinkedList<>(); if (root == null) { return ans; } Deque<TreeNode> q = new LinkedList<>(); q.offerLast(root); while (!q.isEmpty()) { List<Integer> t = new ArrayList<>(); for (int i = q.size(); i > 0; --i) { TreeNode node = q.pollFirst(); t.add(node.val); if (node.left != null) { q.offerLast(node.left); } if (node.right != null) { q.offerLast(node.right); } } ans.addFirst(t); } return ans; } }
-
// OJ: https://leetcode.com/problems/binary-tree-level-order-traversal-ii/ // Time: O(N) // Space: O(N) class Solution { public: vector<vector<int>> levelOrderBottom(TreeNode* root) { if (!root) return {}; vector<vector<int>> ans; queue<TreeNode*> q; q.push(root); while (q.size()) { int cnt = q.size(); ans.emplace_back(); while (cnt--) { root = q.front(); q.pop(); ans.back().push_back(root->val); if (root->left) q.push(root->left); if (root->right) q.push(root->right); } } reverse(begin(ans), end(ans)); return ans; } };
-
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]: ans = [] if root is None: return ans q = deque([root]) while q: t = [] for _ in range(len(q)): node = q.popleft() t.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) ans.append(t) return ans[::-1] ############ # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None from collections import deque class Solution(object): def levelOrderBottom(self, root): """ :type root: TreeNode :rtype: List[List[int]] """ if not root: return [] ans = [[root.val]] queue = deque([root]) while queue: levelans = [] for _ in range(0, len(queue)): root = queue.popleft() if root.left: levelans.append(root.left.val) queue.append(root.left) if root.right: levelans.append(root.right.val) queue.append(root.right) if levelans: ans.append(levelans) return ans[::-1]
-
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func levelOrderBottom(root *TreeNode) [][]int { ans := [][]int{} if root == nil { return ans } q := []*TreeNode{root} for len(q) > 0 { var t []int for i := len(q); i > 0; i-- { node := q[0] q = q[1:] t = append(t, node.Val) if node.Left != nil { q = append(q, node.Left) } if node.Right != nil { q = append(q, node.Right) } } ans = append([][]int{t}, ans...) } return ans }
-
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {number[][]} */ var levelOrderBottom = function (root) { let ans = []; if (!root) return ans; let q = [root]; while (q.length) { let t = []; for (let i = q.length; i > 0; --i) { const node = q.shift(); t.push(node.val); if (node.left) q.push(node.left); if (node.right) q.push(node.right); } ans.unshift(t); } return ans; };