PHP二叉树之构建二叉树

每次刷力扣题，做到链表、二叉树等题目的时候，我就开始发现我无从下手了，我甚至连答案都看不懂！后来我才明白，二叉树是需要自己去构建的。我好菜，我哭死~~

一、准备节点类

很简单，val为当前节点的值，left为左子节点，right为右子节点

/**
 * 节点类
 */
class TreeNode 
{
    public $val = null;
    public $left = null;
    public $right = null;
    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
} 

二、构建二叉树

/**
 * 二叉树
 */
class BinaryTree
{
    public $root;
    public $queue;
    public $index = 0;

    public function __construct(array $data)
    {
        $this->createTree($data);
    }

    public function createTree($arr) 
    {
        if (empty($arr)) {
            return null;
        }

        // 先加入根节点，不管它的左右子节点
        $this->root = new TreeNode($arr[$this->index]);
        // 利用队列来实现，每次处理完父节点，将父节点出列，然后依次压入左、右子节点
        // 然后利用队列可迭代的特性，按照先入先出的特点，循环处理剩余子节点
        $this->queue = new SplQueue;
        $this->queue->enqueue($this->root);

        $len = count($arr);
        while ($this->queue->count() > 0) {
            $cur = $this->queue->dequeue();
            // 左节点
            $this->index++;
            if ($this->index >= $len) {
                $this->index--; // 最大index恢复正常
                break;
            };
            if ($arr[$this->index] !== null) {
                $cur->left = new TreeNode($arr[$this->index]);
                $this->queue->enqueue($cur->left);
            }

            // 右节点
            $this->index++;
            if ($this->index >= $len) {
                $this->index--; // 最大index恢复正常
                break;
            };
            if ($arr[$this->index] !== null) {
                $cur->right = new TreeNode($arr[$this->index]);
                $this->queue->enqueue($cur->right);
            }
        }

        return $this->root;
    }
}

// 用法
$tree = new BinaryTree([1,null,2,3]);
print_r($tree->root);

这样，做二叉树前中后序遍历等题目时，将$tree->root作为入参即可顺利测试啦~