二叉树的深度

题目描述

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

方法一：深度优先搜索（DFS）

<?php

/*class TreeNode{
    var $val;
    var $left = NULL;
    var $right = NULL;
    function __construct($val){
        $this->val = $val;
    }
}*/
function TreeDepth($pRoot)
{
    if(empty($pRoot)) return 0;

    // 树的深度 = max(左子树的深度, 右子树的深度) + 1
    return max(TreeDepth($pRoot->left), TreeDepth($pRoot->right)) + 1;
}

方法二：广度优先搜索（BFS）

每遍历一层，则计数器 +1 ，直到遍历完成，则可得到树的深度。

/**
 * 计算树的深度
 */
function TreeDepth($pRoot)
{
    if (empty($pRoot)) return 0;
    $res = 0;            // 树的深度
    $queue[] = $pRoot;   // 存放每层的节点，初始化为根节点

    while (!empty($queue)) {
        $tmp = [];       // 临时存放当前层的下一层的所有节点
        foreach ($queue as $k) {
            if ($k->left != NULL) $tmp[] = $k->left;
            if ($k->right != NULL) $tmp[] = $k->right;
        }

        $queue = $tmp;   // 当前层往下一层走
        $res++;          // 记录层数
    }
    return $res;
}

测试

<?php

namespace app\index\controller;

class Test
{
  /**
   * 测试
   */
    public function test()
    {
        $pRoot = new TreeNode(3);
        $node1 = new TreeNode(9);
        $node2 = new TreeNode(2);
        $node3 = new TreeNode(1);
        $node4 = new TreeNode(7);

        $pRoot->left  = $node1;
        $pRoot->right = $node2;
        $node2->left  = $node3;
        $node2->right = $node4;
        $this->TreeDepth($pRoot); // 调用
    }
}