关于php:剑指offer之利用广度优先搜索向完全二叉树中添加子节点

问题形容¹

齐全二叉树是每一层（除最初一层外）都是齐全填充（即，节点数达到最大）的，并且所有的节点都尽可能地集中在左侧。

例如：图 1 中的 4 棵二叉树均为齐全二叉树。实现数据结构 CBTInserter 有如下三种办法：

• CBTInserter(Node root) 应用头节点为 root 的给定树初始化该数据结构;
• CBTInserter->insert(val) 向树中插入一个新节点，节点类型为 TreeNode，值为 val。使树放弃齐全二叉树的状态，并返回插入的新节点的父节点的值；
• CBTInserter.get_root() 将返回树的头节点。

图 1

阐明：在 (a) 中的齐全二叉树中增加节点 7 失去 (b)；在 (b) 中的齐全二叉树中增加节点 8 失去 (c)；在 (c) 中的齐全二叉树中增加节点 9 失去 (d)。

什么是齐全二叉树？

在读完题之后，写代码之前须要先搞明确什么是齐全二叉树？

齐全二叉树是由满二叉树而引出来的，若设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数(即 1~h- 1 层为一个满二叉树)，第 h 层所有的结点都间断集中在最右边，这就是齐全二叉树²。

总结：
对于一个深度为 h 的二叉树必须满足以下条件才是齐全二叉树：

1. 1~h-1 层是满二叉树（国内的满二叉树³）。
2. h 层的所有节点都间断集中在最右边。

文字描述有点形象，看几个例子就明确了。

图 2

图中的 (1)(2)(3) 都是齐全二叉树，而 (4)(5)(6) 都不是齐全二叉树。

(1)(2)(3)是齐全二叉树，那必定合乎齐全二叉树的定义。那 (4)(5)(6) 为什么不是呢？咱们一个一个来剖析：

• (4)是一个深度为 4 的二叉树，1~2 层是满二叉树，但第三层不是。不满足 1~4-1 层是一个满二叉树的条件。
• (5)和 (6) 都是深度为 3 的二叉树，1~2 层是一个满二叉树，然而 第 3 层的所有节点 并非间断集中在最右边 。(5) 的第三层最右边都没有节点，而 (6) 的第三层的所有节点不间断。

问题剖析

解决这个问题的关键在于了解齐全二叉树的特点及在二叉树增加节点的程序。

齐全二叉树特点：

1. 1~h-1 层是满二叉树，h 层最多有 2^h-1个节点。
2. h 层的所有节点都间断集中在最右边。

增加程序：

1. 如果最底层节点的个数小于 2 ^h-1个，则从左到右找到该层第一个空缺地位并增加新的节点。
   例如，向图 (1) 中的 (c) 增加节点：
   
   图 3
2. 如果最底层节点的个数为 2 ^h-1，此时再向二叉树增加新的节点会在二叉树中增加新的一层，而且新的节点是新的一层最右边的节点，也就是说，新节点的父节点是原来最上面一层的最右边的节点。
   例如，向图 (1) 中的 (b) 增加节点：
   
   图 4

在齐全二叉树中增加新节点的程序看起来是从上至下，按层从左至右增加的，这就是典型的二叉树广度优先搜寻的程序。

解题思路

1. 在齐全二叉树中依照广度优先搜寻的程序找出第一个左子节点或右子节点还有空缺的节点。
2. 如果该节点没有左子节点，那么新的节点就作为该节点的左子节点；如果该节点没有右子节点，那么新的节点就作为该节点的右子节点。

残缺代码：

<?php
class GBTInserter{private $queue = [];
    private $root;
    public function __construct($root){
        // 利用广度优先搜寻找到第一个短少子节点的节点
        $this->root = $root;
        array_push($this->queue,$root);
        while($this->queuePeek($this->queue)->left != null && $this->queuePeek($this->queue)->right != null){$node = array_shift($this->queue);
            array_push($this->queue,$node->left);
            array_push($this->queue,$node->right);
        }
    } 
    public function queuePeek($queue){
        // 辅助函数，用于返回队列中的第一个元素。return $queue[0];
    } 
    public function insert($val){
        // 增加子节点的逻辑
        $parent = $this->queuePeek($this->queue);
        $node = new Node($val);
        if($parent->left == null){$parent->left = $node;}else{
            $parent->right = $node;
            array_shift($this->queue);
            array_push($this->queue,$parent->left);
            array_push($this->queue,$parent->right);
        }
        return $parent->data;
    }
    public function getRoot(){return $this->root;}
}
// 创立二叉树的类
class Node{
    public $left = NULL;
    public $right = NULL;
    public $data = '';
    public function __construct($data){$this->data = $data;}
    public function buildTree(Node $lchild = NULL,Node $rchild = NULL){if(!is_null($lchild)){$this->left = $lchild;}
        if(!is_null($rchild)){$this->right = $rchild;}
    }
}
// 创立齐全二叉树
$a = new Node(1);
$b = new Node(2);
$c = new Node(3);
$d = new Node(4);
$e = new Node(5);
$f = new Node(6);
$a->buildTree($b,$c);
$b->buildTree($d,$e);
$c->buildTree($f);
$GBTInserter = new GBTInserter($a);
// 增加节点
$GBTInserter->insert(7);
$GBTInserter->insert(8);
$GBTInserter->insert(9);
$re = $GBTInserter->insert(10);

模仿过程

以向图 1 中的 (b) 增加节点为例。

1. GBTInserter 类的构造方法中的广度优先搜索算法是如何找到第一个短少子节点的节点的？
   
   图 5

①. 图 5 中的步骤 (0)，将齐全二叉树的根节点增加到队列中。
②. 根节点 $a 的左右子节点都不为空，于是 $a 出队，将 $a 的左右子节点顺次入队，如图 5 步骤(1) 所示。相干代码如下：

public function __construct($root){
   // 将齐全二叉树的根节点增加到队列中
   array_push($this->queue,$root);
   // 队首的节点的左右子节点都不为空时，继续执行。while($this->queuePeek($this->queue)->left != null && $this->queuePeek($this->queue)->right != null){$node = array_shift($this->queue);
      array_push($this->queue,$node->left);
      array_push($this->queue,$node->right);
   }
}

③. 接下来就是循环解决 $b、$c 节点。因为 $b、$c 节点的左右子节点都不为空，所以过程和解决 $a 节点相似，如图 5 步骤 (2)、步骤(3) 所示。
④. 通过步骤 (3) 之后，队列中保留的全是第 3 层的节点。而队首节点 $d 没有子节点，循环终止。即第一个短少子节点的节点就保留在队列的队首。

2. GBTInserter 类的 insert() 办法是如何增加子节点的：
   在实例化 GBTInserter 类之后，队列中存储的都是短少子节点的节点：

$queue = [$d,$e,$f,$g]

而队首的节点就是第一个短少子节点的节点。而咱们正是要向该节点增加子节点。
①. 利用 queuePeek 办法获取队首节点。
②. 实例化须要增加的节点。

public function insert($val){
   ...
   $parent = $this->queuePeek($this->queue);
   $node = new Node($val);
   ...
}

③. 先问队首节点是否有左子节点？如果没有则增加至左子节点，否则增加到右子节点，并且并且队列 出一入二。

• 出一是指将队首的节点出队，该节点在增加右子节点之后曾经不再短少子节点了，而队列记录的是短少子节点的节点，天然须要将其出队。
• 入二是指将队首节点的左右子节点入队。

④. 返回队首节点的值。

public function insert($val){
   ...
   if($parent->left == null){$parent->left = $node;}else{
       $parent->right = $node;
       array_shift($this->queue);
       array_push($this->queue,$parent->left);
       array_push($this->queue,$parent->right);
   }
   return $parent->data;
}

复杂度剖析

1. 工夫复杂度：

   • GBTInserter 的构造函数从实质上来说是依照广度优先搜寻的程序找出二叉树中所有既有左子节点又有又子节点的节点，因而工夫复杂度为 O(n)。
   • 调用函数 insert 在齐全二叉树中增加一个节点最多只须要在队列中删除一个节点并增加两个节点。通常，队列的插入、删除的工夫复杂度都是 O(1)。
2. GBTInserter 类须要一个队列来实现广度优先搜索算法保留短少左子节点或右子节点的节点，空间复杂度为 O(n)。