[PHP]算法- 二叉树的深度的PHP实现

发布时间：2020-05-25 03:10:11 所属栏目：PHP 来源：互联网

导读：二叉树的深度：输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。思路：1.非递归层序遍历2.使用辅助队列，根结点先入队列3. 循环判断队列是否为空，如果不为空就继续循环队列里面

思路：

1.<span style="color: #000000">非递归层序遍历

2.<span style="color: #000000">使用辅助队列，根结点先入队列

3.<span style="color: #000000"> 循环判断队列是否为空，如果不为空就继续循环队列里面的每个结点

4.<span style="color: #000000"> 循环队列时，当前当前结点出队列，把该结点的左右孩子入队列
TreeDepth(tree)

<span style="color: #0000ff">if !tree <span style="color: #0000ff">return 0

<span style="color: #008080">array_push(queue,<span style="color: #000000">tree);

depth=0

<span style="color: #0000ff">while(!<span style="color: #0000ff">empty<span style="color: #000000">(queue)){

++<span style="color: #000000">depth

<span style="color: #0000ff">for i=0;i<queue.size;i++<span style="color: #000000">

node=<span style="color: #008080">array_pop<span style="color: #000000">(queue)

<span style="color: #008080">array_push(queue,node-><span style="color: #000000">left);

<span style="color: #008080">array_push(queue,node-><span style="color: #000000">right);

<span style="color: #0000ff">return depth

val = TreeDepth((!) 0=(,); =0(!(++=(

            </span><span style="color: #0000ff"&gt;for</span>(<span style="color: #800080"&gt;$i</span>=0;<span style="color: #800080"&gt;$i</span><<span style="color: #800080"&gt;$size</span>;<span style="color: #800080"&gt;$i</span>++<span style="color: #000000"&gt;){
                    </span><span style="color: #800080"&gt;$node</span>=<span style="color: #008080"&gt;array_shift</span>(<span style="color: #800080"&gt;$queue</span>);<span style="color: #008000"&gt;//</span><span style="color: #008000"&gt;非常重要 删除第一个元素</span>
                    <span style="color: #0000ff"&gt;if</span>(<span style="color: #800080"&gt;$node</span>-><span style="color: #000000"&gt;left){
                            </span><span style="color: #008080"&gt;array_push</span>(<span style="color: #800080"&gt;$queue</span>,<span style="color: #800080"&gt;$node</span>-><span style="color: #000000"&gt;left);
                    }   
                    </span><span style="color: #0000ff"&gt;if</span>(<span style="color: #800080"&gt;$node</span>-><span style="color: #000000"&gt;right){
                            </span><span style="color: #008080"&gt;array_push</span>(<span style="color: #800080"&gt;$queue</span>,<span style="color: #800080"&gt;$node</span>-><span style="color: #000000"&gt;right);
                    }   
            }   
    }    
    </span><span style="color: #0000ff"&gt;return</span> <span style="color: #800080"&gt;$depth</span><span style="color: #000000"&gt;;

}

$node1=new TreeNode(1);
$node2=new TreeNode(2);
$node3=new TreeNode(3);
$node4=new TreeNode(4);
$node5=new TreeNode(5);
$node6=new TreeNode(6);
$node7=new TreeNode(7);

$tree=$node1;
$node1->left=$node2;
$node1->right=$node3;
$node2->left=$node4;
$node2->right=$node5;
$node4->right=$node6;
$node3->left=$node7;

var_dump($tree);
$dep=TreeDepth($tree);
var_dump($dep);

（编辑：安卓应用网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!