create return type that carries two attributes maxLeftDepth and maxLeftNodeVale


  • 0
    C

    The ReturnType class will store the max left node depth along with the node value, divide and conquer through the tree, the final return node value is the answer

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        class ReturnType {
            int maxLeftDepth;
            int maxLeftValue;
            
            public ReturnType(int maxLeftDepth, int maxLeftValue) {
                this.maxLeftDepth = maxLeftDepth;
                this.maxLeftValue = maxLeftValue;
            }
        }
        public int findBottomLeftValue(TreeNode root) {
            
            ReturnType ans = dfs(root);
            return ans.maxLeftValue;
        }
        
        public ReturnType dfs(TreeNode root) {
            if (root == null) {
                return new ReturnType(0, 0);
            }    
            
            ReturnType left = dfs(root.left);
            ReturnType right = dfs(root.right);
            
            if (left.maxLeftDepth == 0 && right.maxLeftDepth == 0) {
                return new ReturnType(1, root.val);
            }
            
            if (left.maxLeftDepth >= right.maxLeftDepth) {
                return new ReturnType(left.maxLeftDepth + 1, left.maxLeftValue);
            }
            
            return new ReturnType(right.maxLeftDepth + 1, right.maxLeftValue);
            
            
            
        }
    }
    

Log in to reply
 

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