Java code with explanation


  • 0
    L

    We have some good solutions here but I find it harder to read the code with the global variable in a recursive function. So I will try explaining my version in case it makes sense to someone. The idea is that the longest path (or the diameter) may or may not pass via the root. So it means we have 3 values to compare and find a max among: left diameter, right diameter or the sum of all nodes from left to right tree while passing through the root.

    public class Solution {
        public int diameterOfBinaryTree(TreeNode root) {
            if(root==null) {
                return 0;
            }
            int leftDiameter = diameterOfBinaryTree(root.left);
            int rightDiameter = diameterOfBinaryTree(root.right);
            int rootHeight = maxdepth(root.left) + maxdepth(root.right);
            
            return Math.max(leftDiameter,Math.max(rightDiameter,rootHeight));
        }
        
        private int maxdepth(TreeNode root) {
            if(root==null) {
                return 0;
            }        
            return 1+ Math.max(maxdepth(root.left),maxdepth(root.right));
        }
    }
    

Log in to reply
 

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