Java solution with explanation


  • 0

    Let us define the diameter of each node as the sum of the longest paths in it's left and right subtrees.
    Thus, d = longestPath(left) + longestPath(right)
    The diameter of the tree is the max of all such d's

    public class Solution {
        public int diameterOfBinaryTree(TreeNode root) {
            Map<TreeNode, Integer> longestPaths = new HashMap<>();
            int result = 0;
            longestPath(root, longestPaths);
            for(TreeNode node : longestPaths.keySet()) {
                int d = 0;
                if(node.left != null) {
                    d += (1 + longestPaths.get(node.left));
                }
                if(node.right != null) {
                    d += (1 + longestPaths.get(node.right));
                }
                result = Math.max(result, d);
            }
            
            return result;
        }
        
        private int longestPath(TreeNode node, Map<TreeNode, Integer> longestPaths) {
            if(node == null) {
                return -1;
            }
            
            int result = Math.max(1 + longestPath(node.left, longestPaths), 1 + longestPath(node.right, longestPaths));
            longestPaths.put(node, result);
            
            return result;
        }
    }
    

Log in to reply
 

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