Java DFS solution - store depth of each level


  • 0
    public class Solution {
        public int findBottomLeftValue(TreeNode root) {
            Stack<TreeNode> stack = new Stack<>();
            Map<TreeNode, Integer> depths = new HashMap<>();
            TreeNode curr = root;
            int currDepth = 0;
            int maxDepth = 0;
            TreeNode bottomLeft = root;
            do {
                if(curr != null) {
                    stack.push(curr);
                    depths.put(curr, currDepth);
                    curr = curr.left;
                    currDepth++;
                }
                else {
                    TreeNode popped = stack.pop();
                    currDepth = depths.get(popped);
                    if(currDepth > maxDepth) {
                        maxDepth = currDepth;
                        bottomLeft = popped;
                    }
                    curr = popped.right;
                    currDepth++;
                }
            } while(!stack.isEmpty() || curr != null); //case when rightmost leaf reached
            
            return bottomLeft.val;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.