Java Solution without calculating height on each node


  • 0
    K

    class Solution {

    static class retVal {
        int oneside = 0;
        int mymax = 0;
        
        public retVal(int x, int y)
        {
            oneside = x;
            mymax = y;
        }
    }
    
    public int diameterOfBinaryTree(TreeNode root) {
        
        if(root==null)
        {
            return 0;
        }
        retVal t = helper(root);
        
        return Math.max(t.oneside,t.mymax)-1;
    }
    
    public static retVal helper(TreeNode root)
    {
        if(root==null)
        {
            retVal t = new retVal(0,0);
            return t;
        }
        
        retVal left = helper(root.left);
        retVal right = helper(root.right);
        
        int myMax = left.oneside + right.oneside + 1;
        int myOne = Math.max(left.oneside,right.oneside) + 1; 
        
        int tmp = Math.max(left.mymax,right.mymax);
        myMax = Math.max(tmp,myMax);
        retVal ans = new retVal(myOne,myMax);
        return ans;
    }
    

    }


Log in to reply
 

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