剑指Offer - PHP二叉树的下一个节点
题目描述
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
分析
下图二叉树的中序遍历为：{D,B,H,E,I,A,F,C,G}
中序遍历类型总结：
有右子树，下一结点是右子树中的最左结点，例如 B，下一结点是 H。
无右子树，且结点是该结点父结点的左子树，则下一结点是该结点的父结点，例如 H，下一结点是 E。
无右子树，且结点是该结点父结点的右子树，则我们一直沿着父结点追朔，直到找到某个结点是其父结点的左子树，如果存在这样的结点，那么这个结点的父结点就是我们要找的下一结点。例如 I，下一结点是 A；例如 G，并没有符合情况的结点，所以 G 没有下一结点。
代码
class TreeLinkNode{
var $val;
var $left = NULL;
var $right = NULL;
var $next = NULL; // 指向父节点
function __construct($x){
$this->val = $x;
}
}<?php
namespace app\controller;
class Index
{
/**
* 获取给定节点的下一节点
* @param object $pNode TreeLinkNode对象
*/
function GetNext($pNode)
{
if (!$pNode) return null;
// 如果当前节点有右子树，则下一节点在右子树的最左边。
if ($pNode->right != null) {
$pNode = $pNode->right;
while ($pNode->left != null) {
$pNode = $pNode->left;
}
return $pNode;
}
// 如果当前节点有左子树，则判断当前节点是父节点的左节点还是右节点。
while ($pNode->next != null) {
// 如果当前节点是父节点的左节点，则下一节点就是父节点。
if ($pNode->next->left == $pNode) {
return $pNode->next;
}
// 如果当前节点是父节点的右节点，则再找父节点的父节点。
$pNode = $pNode->next;
}
// 没有下一节点
return null;
}
}
关于 LearnKu
粤公网安备 44030502004330号