Binary Tree Level Order Traversal II – Leetcode Solution

In this post, we are going to solve the 107. Binary Tree Level Order Traversal II problem of Leetcode. This problem 107. Binary Tree Level Order Traversal II is a Leetcode medium level problem. Let’s see the code, 107. Binary Tree Level Order Traversal II – Leetcode Solution.

Problem

Given the root of a binary tree, return the bottom-up level order traversal of its nodes’ values. (i.e., from left to right, level by level from leaf to root).

Example 1 :

Input: root = [3,9,20,null,null,15,7]
Output: [[15,7],[9,20],[3]]

Example 2 :

Input: root = [1]
Output: [[1]]

Example 3 :

Input: root = []
Output: []

Constraints

  • The number of nodes in the tree is in the range [0, 2000].
  • -1000 <= Node.val <= 1000

Now, let’s see the code of 107. Binary Tree Level Order Traversal II – Leetcode Solution.

Binary Tree Level Order Traversal II – Leetcode Solution

107. Binary Tree Level Order Traversal II – Solution in Java

/**
 * 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) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        Stack<List<Integer>> s = new Stack<>();
       if(root == null) return ans;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            int size = q.size();
            List<Integer> level = new ArrayList<Integer>();
            while(size-- > 0){
                TreeNode rn = q.poll();
                level.add(rn.val);
                if(rn.left != null) q.add(rn.left);
                if(rn.right != null) q.add(rn.right);
            }
             
            ans.add(0,level);
        }
        return ans;
    }
}

107. Binary Tree Level Order Traversal II – Solution in C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int height(TreeNode* root){
        if(root == NULL) return 0;
        
        return max(height(root->left),height(root->right)) + 1;
    }
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        int n = height(root);
        vector<vector<int>> ans(n);
        if(root == NULL) return ans;
        
        queue<TreeNode*>qu;
        qu.push(root);
        while(!qu.empty()){
            int sz = qu.size();
            vector<int>level;
            for(int i=0;i<sz;i++){
                TreeNode* front = qu.front();
                qu.pop();
                level.push_back(front->val);
                if(front->left) qu.push(front->left);
                if(front->right) qu.push(front->right);
            }
            ans[n-1] = level;
            n--;
        }
        return ans;
    }
};

107. Binary Tree Level Order Traversal II – Solution in Python

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def levelOrderBottom(self, root):
        queue, res = collections.deque([(root, 0)]), []
        while queue:
            node, level = queue.popleft()
            if node:
                if len(res) < level+1:
                    res.insert(0, [])
                res[-(level+1)].append(node.val)
                queue.append((node.left, level+1))
                queue.append((node.right, level+1))
        return res
        

Note: This problem 107. Binary Tree Level Order Traversal II is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.

Leave a Comment

Your email address will not be published.