Recursive, modular Java solution


  • 0
    A

    This is the solution I came up with. My logic is this: at a node (say x), calculate the sum of heights of x's left and right subtrees (that would be the max length of a path between two leaves that contains the node x). Update "max" to the current path length if it is greater than max. Do this at every node, and finally return the max.

    public int diameterOfBinaryTree(TreeNode root) {
        if(root == null) return 0;
        
        int[] max = new int[]{0};
        diameterOfBinaryTree(root, max);
        return max[0];
    }
    
    private void diameterOfBinaryTree(TreeNode root, int[] max) {
        int diam = height(root.left) + height(root.right);
        max[0] = Math.max(max[0], diam);
    
        if(root.left != null)
            diameterOfBinaryTree(root.left, max);
            
        if(root.right != null)
            diameterOfBinaryTree(root.right, max);            
    }
    
    private int height(TreeNode root) {
        if(root == null) return 0;
        
        return 1 + Math.max(height(root.left), height(root.right));
    }

  • 0
    L

    Why do you need to check root.left==null?


Log in to reply
 

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