# 二叉搜索树的第k个节点

## 示例

{5,3,7,2,4,6,8},3

{4}

## 解法一：中序遍历

``````class TreeNode{
var \$val;
var \$left  = NULL;
var \$right = NULL;

function __construct(\$val){
\$this->val = \$val;
}
}``````
``````<?php

namespace app\controller;

class Index
{
/**
* 中序遍历
*/
public function LDR(\$pRoot, &\$list)
{
if (\$pRoot == null) return null;

\$this->LDR(\$pRoot->left, \$list);
\$list[] = \$pRoot;
\$this->LDR(\$pRoot->right, \$list);
return \$list;
}
}``````
``````    /**
* 测试
*/
public function test()
{
// 构造二叉搜索树
\$root  = new TreeNode(5);
\$node3 = new TreeNode(3);
\$node7 = new TreeNode(7);
\$node2 = new TreeNode(2);
\$node4 = new TreeNode(4);
\$node6 = new TreeNode(6);
\$node8 = new TreeNode(8);

\$root->left  = \$node3;
\$root->right = \$node7;
\$node3->left  = \$node2;
\$node3->right = \$node4;
\$node7->left  = \$node6;
\$node7->right = \$node8;

\$k    = 3;  // 第 k 小节点
\$list = []; // 存放中序遍历节点

\$this->LDR(\$root, \$list);
echo \$list[\$k - 1];
}``````

## 解法二：优化中序遍历

``````<?php

namespace app\controller;

class Index
{
/**
* 中序遍历优化
*/
public function KthNode(\$pRoot, &\$k)
{
if (!\$pRoot) return null;

\$t = \$this->KthNode(\$pRoot->left, \$k);  // 递归到最左节点
if (\$t) return \$t;                      // 如果上一行代码在递归中满足(--\$k==0)，则 \$t不为 null。
if (--\$k == 0) return \$pRoot;           // 判断是否递归到第 k 个节点

\$t = \$this->KthNode(\$pRoot->right, \$k); // 递归右节点
if (\$t) return \$t;
}
}``````

## 测试

``````    /**
* 测试
*/
public function test()
{
\$root  = new TreeNode(5);
\$node3 = new TreeNode(3);
\$node7 = new TreeNode(7);
\$node2 = new TreeNode(2);
\$node4 = new TreeNode(4);
\$node6 = new TreeNode(6);
\$node8 = new TreeNode(8);

\$root->left   = \$node3;
\$root->right  = \$node7;
\$node3->left  = \$node2;
\$node3->right = \$node4;
\$node7->left  = \$node6;
\$node7->right = \$node8;

\$k   = 1;
\$res = \$this->KthNode(\$root, \$k);
print_r(\$res);
}``````