PHP实现二叉树遍历获取所有叶子节点问题求助

现有代码问题排查 #

• 内存溢出根源：getLeafs()方法未定义入参，递归调用时传入根节点触发无限递归，不断重复判断根节点的子节点状态，直接耗尽内存
• 插入逻辑缺陷：原有setNode()仅能处理节点左右子节点存在空缺的场景，当父节点左右都已填充时没有向下遍历逻辑，无法完成满二叉树的层序插入
• 空值处理错误：测试数组中的null值会被直接实例化为Node节点，不符合常规二叉树空节点的定义

修复后完整代码 #

<?php

class Node
{
    public $value;
    public $left;
    public $right;

    public function __construct($item)
    {
        $this->value = $item;
        $this->left = null;
        $this->right = null;
    }
}

class Tree
{
    protected $root;
    public $leafs;
    // 插入队列维护待填充子节点的父节点
    protected $insertQueue;

    public function __construct()
    {
        $this->root = null;
        $this->leafs = [];
        $this->insertQueue = [];
    }

    public function isEmpty()
    {
        return $this->root === null;
    }

    public function insert($node)
    {
        // 跳过空值节点
        if ($node->value === null) {
            return;
        }
        if ($this->isEmpty()) {
            $this->root = $node;
            array_push($this->insertQueue, $this->root);
            return;
        }
        $parent = $this->insertQueue[0];
        if ($parent->left === null) {
            $parent->left = $node;
            array_push($this->insertQueue, $parent->left);
        } else if ($parent->right === null) {
            $parent->right = $node;
            array_push($this->insertQueue, $parent->right);
            // 父节点左右填满后出队，切换下一个待填充节点
            array_shift($this->insertQueue);
        }
    }

    public function getLeafs($node = null)
    {
        // 初始调用默认使用根节点，重置结果集避免多次调用数据叠加
        if ($node === null) {
            $node = $this->root;
            $this->leafs = [];
        }
        if ($node === null) {
            return $this;
        }
        // 判断是否为叶子节点
        if ($node->left === null && $node->right === null) {
            array_push($this->leafs, $node->value);
            return $this;
        }
        // 递归遍历左右子树
        if ($node->left !== null) {
            $this->getLeafs($node->left);
        }
        if ($node->right !== null) {
            $this->getLeafs($node->right);
        }
        return $this;
    }
}

$tree1 = new Tree();
$items1 = [3, 5, 1, 6, 2, 9, 8, null, null, 7, 4];

foreach ($items1 as $item) {
    $node = new Node($item);
    $tree1->insert($node);
}

$tree2 = new Tree();
$items2 = [3, 5, 1, 6, 7, 4, 2, null, null, null, null, null, null, 9, 8];

foreach ($items2 as $item) {
    $node = new Node($item);
    $tree2->insert($node);
}

print_r($tree1->getLeafs()->leafs);
// 输出结果：Array ( [0] => 6 [1] => 7 [2] => 4 [3] => 9 [4] => 8 )

内容的提问来源于stack exchange，提问作者GolDRoger