把二叉树打印成多行

题目描述

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

示例

输入

{8,6,10,5,7,9,11}

输出

[[8],[6,10],[5,7,9,11]]

分析

层序遍历：从上到下，从左至右打印每一层节点。有深度优先搜索（DFS），也有广度优先搜索（BFS）。

广度优先搜索

/**
 * 节点
 */
class TreeNode{
    var $val;
    var $left = NULL;
    var $right = NULL;

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

写法一

利用计数变量打印节点。

• 数组变量$queue，存放需要遍历的节点（相当于队列）。
• 数组变量$list，存放最终要输出的值。
• 数组变量$tempList，存放每一层的节点，然后再放到$list。
• 整型变量$toBePrinted，计算当前层还有几个节点没打印。
• 整型变量$nextLevel，统计下一层需要打印的节点数。

<?php

namespace app\controller;

class Index
{
    /**
     * 广度优先搜索
     *
     * @param $pRoot
     * @return null
     */
    public function BFS($pRoot)
    {
        if ($pRoot == null) return null;

        $nextLevel   = 0;        // 下一层节点的数目。
        $toBePrinted = 1;        // 当前层需要打印的节点数
        $list        = [];       // 存放结果的数组。
        $queue       = [$pRoot]; // 需要打印的节点队列，初始值为根节点。
        $tempList    = [];       // 临时数组：存放每一层的节点。

        while (!empty($queue)) {                // 当队列不为空。
            $currentRoot = array_shift($queue); // 拿出数组第一个元素，相当于队列中的出列。
            $tempList[]  = $currentRoot->val;   // 存放当前节点值。

            if ($currentRoot->left) {           // 如果当前节点有左节点。
                $nextLevel++;                   // 下一层节点的数目 +1。
                $queue[] = $currentRoot->left;  // 将左节点放入队列。
            }
            if ($currentRoot->right) {
                $nextLevel++;
                $queue[] = $currentRoot->right;
            }

            $toBePrinted--;                     // 当前层打印的节点数目 -1。
            if ($toBePrinted == 0) {            // 如果当前层的节点全部打印完。
                $list[] = $tempList;            // 将临时数组放入结果数组，并清空临时数组。
                unset($tempList);
                $toBePrinted = $nextLevel;      // 将下一层需要打印的节点数赋值给 $toBePrinted
                $nextLevel   = 0;               // 重新计算下一层节点的数目
            }
        }

        return $list;
    }
}

写法二

利用队列打印节点数。

<?php

namespace app\controller;

class Index
{
    /**
     * 广度优先搜索
     *
     * @param $pRoot
     * @return null
     */
    public function BFS($pRoot)
    {
        if ($pRoot == null) return [];

        $queue = new \SplQueue();
        $queue->enqueue([$pRoot]);                    // 初始化：第一层放根节点
        $list = [];                                   // 存放结果数组

          while (!$queue->isEmpty()) {
            $currentRoot        = $queue->dequeue();  // 取出队列头节点
            list($level, $node) = each($currentRoot); // 键为层级，值为节点
            $list[$level][]     = $node->val;         // 放入结果数组

            if ($node->left) $queue->enqueue([$level + 1 => $node->left]);  // 左节点放入队列，层级加1
            if ($node->right) $queue->enqueue([$level + 1 => $node->right]);// 右节点放入队列，层级加1
        }

        return $list;
    }
}