PHP中二叉树遍历需先定义TreeNode类，含val、left、right属性；递归实现前序（根→左→右）、中序（左→根→右）、后序（左→右→根）；迭代用栈模拟，层序用队列实现广度优先遍历。
二叉树节点定义与基础结构
在 PHP 中实现二叉树遍历前，需先定义节点类。每个节点包含数据（val）、左子节点（left）和右子节点（right）：
class TreeNode {
public $val;
public $left;
public $right;
public function __construct($val = 0, $left = null, $right = null) {
$this->val = $val;
$this->left = $left;
$this->right = $right;
}
}
这是所有遍历算法的共同前提。构建树时，按需 new 节点并连接左右引用即可。
递归方式实现三种经典遍历
深度优先遍历的三种顺序——前序、中序、后序——用递归最直观，逻辑清晰：
- 前序遍历（根→左→右）：先访问当前节点值，再递归左子树，最后递归右子树
- 中序遍历（左→根→右）：先递归左子树，再访问当前节点，最后递归右子树；对二叉搜索树而言，结果自然有序
- 后序遍历（左→右→根）：先递归左右子树，最后访问当前节点；常用于释放树内存或计算子树信息
示例中序遍历函数：
立即学习“PHP免费学习笔记（深入）”；
function inorderTraversal($root) {
$result = [];
$inorder = function($node) use (&$result, &$inorder) {
if ($node === null) return;
$inorder($node->left);
$result[] = $node->val;
$inorder($node->right);
};
$inorder($root);
return $result;
}
迭代方式用栈模拟递归过程
递归本质依赖调用栈，迭代则需显式使用 PHP 数组模拟栈。关键在于控制节点访问时机：
- 前序迭代：入栈根节点；每次弹出一个节点，将其值加入结果，再按「右→左」顺序压入非空子节点（保证左先被处理）
- 中序迭代：不立即访问节点，而是沿左链一路压栈到底；弹出时访问，再转向右子树继续压栈
- 后序迭代稍复杂：可采用「前序变体 + 反转」——按「根→右→左」压栈遍历，最后将结果数组反转
中序迭代简写示例：
function inorderTraversalIterative($root) {
$result = [];
$stack = [];
$current = $root;
while ($current !== null || !empty($stack)) {
while ($current !== null) {
$stack[] = $current;
$current = $current->left;
}
$current = array_pop($stack);
$result[] = $current->val;
$current = $current->right;
}
return $result;
}
层序遍历（广度优先）用队列实现
层序遍历按从上到下、从左到右逐层访问，适合用队列（PHP 中用数组 + array_shift() 或 SplQueue）：
- 初始化队列，推入根节点
- 循环直到队列为空：弹出队首节点，记录其值；若它有左/右子节点，依次入队
- 如需区分每层，可在每轮循环开始前记录当前队列长度，只处理该长度个节点
基础层序代码：
function levelOrder($root) {
if ($root === null) return [];
$result = [];
$queue = [$root];
while (!empty($queue)) {
$node = array_shift($queue);
$result[] = $node->val;
if ($node->left !== null) $queue[] = $node->left;
if ($node->right !== null) $queue[] = $node->right;
}
return $result;
}
