In this Leetcode Binary Tree Level Order Traversal II problem solution we have Given the root of a binary tree, return the bottom-up level order traversal of its nodes’ values.
Problem solution in Python.
class Solution: def levelOrderBottom(self, root): result = [] if root == None: return result def bfsbottomup(result, prev): if prev == []: return temp = [] cur = [] for node in prev: temp.append(node.val) if node.left != None: cur.append(node.left) if node.right != None: cur.append(node.right) bfsbottomup(result, cur) result.append(temp) bfsbottomup(result, [root]) return result
Problem solution in Java.
class Solution { LinkedList ans = new LinkedList(); Queue<TreeNode> q = new ArrayDeque(); public List<List<Integer>> levelOrderBottom(TreeNode root) { if(root == null) return ans; q.offer(root); while(!q.isEmpty()){ List <Integer>tmp = new ArrayList(); int size = q.size(); for(int i = 0 ; i < size; i++){ TreeNode node = q.poll(); tmp.add(node.val); if(node.left != null){ q.add(node.left); } if(node.right != null){ q.add(node.right); } } ans.addFirst(tmp); } return ans; } }
Problem solution in C++.
vector<vector<int>> levelOrderBottom(TreeNode* root) { vector<vector<int>> result; queue<pair<TreeNode*,int>> toVisit; toVisit.push(make_pair(root,0)); while(!toVisit.empty()) { TreeNode *atNode = toVisit.front().first; int level = toVisit.front().second; toVisit.pop(); if(!atNode) { continue; } if(result.size() <= level) { vector<int> empty; result.push_back(empty); } result[level].push_back(atNode->val); toVisit.push(make_pair(atNode->left,level+1)); toVisit.push(make_pair(atNode->right,level+1)); } for(int i=0; i<result.size()/2; i++) { vector<int> temp = result[i]; result[i] = result[result.size()-i-1]; result[result.size()-i-1] = temp; } return result; }
Problem solution in C.
int maxDepth(struct TreeNode* root) { if (root==NULL) return 0; else { int L=maxDepth(root->left); int R=maxDepth(root->right); int M=(L>R)?L:R; return M+1; } } int** levelOrderBottom(struct TreeNode* root, int** columnSizes, int* returnSize) { if (root==NULL) return NULL; int depth=*returnSize=maxDepth(root); int** res=(int**)calloc(depth,sizeof(int*)); *columnSizes=(int*)calloc(depth,sizeof(int)); struct TreeNode* queue[5000]; int front=0,rear=0; queue[rear++]=root; int cur_size=1;int next_size=0;int size=depth-1; while (front<rear) { res[size]=(int*)malloc(2000*sizeof(int)); for (int i=0;i<cur_size&&front<rear;i++) { struct TreeNode* temp=queue[front++]; res[size][i]=temp->val; if (temp->left) { queue[rear++]=temp->left; next_size++; } if (temp->right) { queue[rear++]=temp->right; next_size++; } } (*columnSizes)[size--]=cur_size; cur_size=next_size; if (cur_size==0) break; next_size=0; } return res; }