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

Examples

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

Output: 5

Solutions

// 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;
		}
}

/**
 * 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

Previous536. Construct Binary Tree from String Next545. Boundary of Binary Tree

Last updated 4 years ago

Was this helpful?