_107. Binary Tree Level Order Traversal II.md

107. Binary Tree Level Order Traversal II

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : July 04, 2024

Last updated : July 04, 2024

---

Related Topics : Tree, Breadth-First Search, Binary Tree

Acceptance Rate : 65.43 %

---

This also could have easily been done by reversing the left-right traversal order, then just using the default Collections reverse function to have the deepest layers appear first.

---

Solutions

• m107.java

Java

m107.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) {
        HashMap<Integer, List<Integer>> levelOrderVals = new HashMap<>();
        int maxDepth = helper(root, 0, levelOrderVals);

        List<List<Integer>> output = new LinkedList<>();
        for (int i = maxDepth; i >= 0; i--) {
            output.add(levelOrderVals.get(i));
        }

        return output;
    }

    private int helper(TreeNode curr, int depth, HashMap<Integer, List<Integer>> levelOrderVals) {
        if (curr == null) {
            return depth - 1;
        }
        if (!levelOrderVals.containsKey(depth)) {
            levelOrderVals.put(depth, new LinkedList<Integer>());
        }
        levelOrderVals.get(depth).add(curr.val);

        depth++;
        return Integer.max(helper(curr.left, depth, levelOrderVals), helper(curr.right, depth, levelOrderVals));
    }
}