FRTKL

543. Diameter of Binary Tree (Easy)

Problem

https://leetcode.com/problems/diameter-of-binary-tree/

  • 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.

Example: Given a binary tree

          1
         / \
        2   3
       / \     
      4   5    
  • Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].
  • Note: The length of path between two nodes is represented by the number of edges between them.

Solution

Go

// 割愛

PHP

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

    /**
     * @param TreeNode $root
     * @return Integer
     */
    
    function diameterOfBinaryTree($root) {
        // $max = 二点間のノードの最も長い経路(初期値=0にすると空がinputされた時に-1になってしまうので1とする)
        $max = 1;
        
        // 渡されたノードの深さを計算する
        // 引数で渡した$maxに、二点間のノードの最も長い経路を計算する関数
        $this->calculate($root, $max);

        // $maxは二点間のノードの最も長い経路なので、ノードからノードまでに必要な長さは-1する
        return $max - 1;
    }
    
    function calculate($node, &$max) {
        // ノードが終点だったら深さは0
        if (is_null($node)) {
            return 0;
        } 
        
        // 渡されたノードの左側の深さを計算する
        $left = $this->calculate($node->left, $max);
        // 渡されたノードの右側の深さを計算する
        $right = $this->calculate($node->right, $max);

        // ルートノードを通らない最長経路の場合が存在するため
        // $left + $rightが$maxを超えた場合のみ$maxを上書きする
        // ※再帰関数のため最後はルートノードの計算となる。必ず上書きすると正しく動かなくなる
        if ($left + $right + 1 > $max) {
            $max = $left + $right + 1;
        }

        // ノードの深さ(左右どちらかの最大値) + 自身の1を返す
        return max($left, $right) + 1;
    }
}

Impression

Written By Fukuaki TAKANO
fortkle icon

Engineering Manager at Connehito inc.
Please contact me via twitter. @fortkle