LeetCode-in-All

543. Diameter of Binary Tree

Easy

Given the root of a binary tree, return 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.

The length of a path between two nodes is represented by the number of edges between them.

Example 1:

Input: root = [1,2,3,4,5]

Output: 3

Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

Example 2:

Input: root = [1,2]

Output: 1

Constraints:

Solution

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($val = 0, $left = null, $right = null) {
 *         $this->val = $val;
 *         $this->left = $left;
 *         $this->right = $right;
 *     }
 * }
 */
class Solution {
    private $diameter;

    /**
     * @param TreeNode $root
     * @return Integer
     */
    public function diameterOfBinaryTree($root) {
        $this->diameter = 0;
        $this->diameterOfBinaryTreeUtil($root);
        return $this->diameter;
    }

    private function diameterOfBinaryTreeUtil($root) {
        if ($root == null) {
            return 0;
        }
        $leftLength = $root->left != null ? 1 + $this->diameterOfBinaryTreeUtil($root->left) : 0;
        $rightLength = $root->right != null ? 1 + $this->diameterOfBinaryTreeUtil($root->right) : 0;
        $this->diameter = max($this->diameter, $leftLength + $rightLength);
        return max($leftLength, $rightLength);
    }
}