543. Diameter of Binary Tree

Description

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: [1, 2, 3, 4, 5, null, null, 6, null, null, null, 7]

Output: 5

Example 2

Input: []

Output: 0

Example 3

Input: [1]

Output: 0

Example 4

Input: [1, 2, 3, 4, 5, 6, 7]

Output: 4

Solutions

TreeNode

// Definition for a binary tree node.
public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;
		TreeNode() {}
		TreeNode(int val) { 
				this.val = val;
		}
		TreeNode(int val, TreeNode left, TreeNode right) {
				this.val = val;
				this.left = left;
				this.right = right;
		}
}

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    private int diameter = 0;
    
    public int diameterOfBinaryTree(TreeNode root) {
        getDiameter(root);
        return diameter;
    }
    
    private int getDiameter(TreeNode node) {
        if(node == null) {
            return 0;
        }
        
        int lh = getDiameter(node.left);
        int rh = getDiameter(node.right);
        
        diameter = Math.max(diameter, lh+rh);
        
        return 1 + Math.max(lh, rh);
    }
}

Follow up