Find deepest left node by level aware node


  • 0

    It is possible to compare the deepness of 2 node and choose the deepest one, by keeping the level awareness in node. This solution uses more memory though.
    (This could have been also implemented as <TreeNode, Integer> map to keep levels up to nodes, but that would cause boxing.)

    class Solution {
        
        class LevelNode {
            public int level;
            public TreeNode node;
            LevelNode(int level, TreeNode node) {
                this.level = level;
                this.node = node;
            }
        }
        
        public int findBottomLeftValue(TreeNode root) {
            return getDeepestLeft(new LevelNode(0, root)).node.val;
        }
        
        private LevelNode getDeepestLeft(LevelNode levelNode) {
            if(levelNode.node.left == null && levelNode.node.right == null) return levelNode;
            
            int nextLevel = levelNode.level + 1;
            if(levelNode.node.left == null) {
                return getDeepestLeft(new LevelNode(nextLevel, levelNode.node.right)); 
            } else if(levelNode.node.right == null) {
                return getDeepestLeft(new LevelNode(nextLevel, levelNode.node.left));
            } else {
                LevelNode fromLeft = getDeepestLeft(new LevelNode(nextLevel, levelNode.node.left));
                LevelNode fromRight = getDeepestLeft(new LevelNode(nextLevel, levelNode.node.right)); 
            
                return (fromLeft.level >= fromRight.level) ? fromLeft : fromRight;
            }
        }
    }
    

Log in to reply
 

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