二叉树深度

TreeNode.php

<?php
namespace Tree;

Class TreeNode {
    public int $val;

    public ?TreeNode $left = null;
    public ?TreeNode $right = null;

    public function __construct(int $x)
    {
        $this->val = $x;
    }
}

$first  = new TreeNode(1);
$second = new TreeNode(2);
$third  = new TreeNode(3);

$first->right = $second;
$second->left = $third;

   //     1
   //      \
   //       2
   //      /
   //     3

<?php
require 'TreeNode.php';

use Tree\TreeNode;

Class Depth{
    public function Recursive(?TreeNode $root) : int
    {
        if (empty($root)) return 0;

        $left_height = $this->Recursive($root->left);
        $right_height = $this->Recursive($root->right);

        return max($left_height, $right_height) + 1;
    }

    public function Interation(TreeNode $root) : int
    {
        $stack = [];
        if ( boolval($root) ) {
            array_push($stack, [1, $root]);
        }

        $depth = 0;

        while (boolval($stack)) {
            list($cur_dep, $root) = array_pop($stack);
            if (boolval($root)) {
                $depth = max($depth, $cur_dep);
                array_push($stack, [$cur_dep + 1, $root->left]);
                array_push($stack, [$cur_dep + 1, $root->right]);
            }
        }

        return $depth;
    }
}

$test = new Depth();


print_r($test->Recursive($first));
echo PHP_EOL;
print_r($test->Interation($first));

本作品采用《CC 协议》，转载必须注明作者和本文链接