剑指offer-62、⼆叉搜索树的第k个结点
<h2 id="题描述">题⽬描述</h2><p>给定⼀棵⼆叉搜索树，请找出其中的第 k ⼩的 TreeNode 结点。</p>
<p>示例1<br>
输⼊：{5,3,7,2,4,6,8},3<br>
返回值：{4}</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="二叉搜索树的关键性质">二叉搜索树的关键性质</h3>
<p>二叉搜索树具有一个重要特性：<strong>中序遍历（左-根-右）BST会得到一个升序排列的节点值序列</strong>。因此，寻找第k小的节点本质上就是获取中序遍历序列中的第k个元素。理解这一点是掌握所有解法的基石。</p>
<h3 id="递归中序遍历直观版">递归中序遍历（直观版）</h3>
<p><strong>算法思路</strong>：</p>
<ol>
<li>进行递归中序遍历</li>
<li>将遍历到的节点值依次加入一个列表。</li>
<li>遍历完成后，列表中的元素就是升序排列的。</li>
<li>从列表中取出第k-1个元素（索引从0开始）即为答案。</li>
</ol>
<pre><code class="language-java">class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public int kthSmallest(TreeNode root, int k) {
// 用于存储中序遍历结果的列表
List<Integer> inorderList = new ArrayList<>();
// 执行中序遍历
inorderTraversal(root, inorderList);
// 返回第k小的元素（列表索引从0开始，所以是k-1）
return inorderList.get(k - 1);
}
/**
* 递归中序遍历二叉树
* @param node 当前遍历的节点
* @param list 存储遍历结果的列表
*/
private void inorderTraversal(TreeNode node, List<Integer> list) {
if (node == null) {
return; // 递归终止条件：遇到空节点则返回
}
inorderTraversal(node.left, list);// 递归遍历左子树
list.add(node.val); // 访问当前节点，将值加入列表
inorderTraversal(node.right, list); // 递归遍历右子树
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)。需要遍历树中的所有n个节点。</li>
<li><strong>空间复杂度</strong>：O(n)。主要取决于递归调用栈的深度（最坏情况为O(n)，树退化成链表）和存储遍历结果的列表（O(n)）。</li>
</ul>
<h3 id="迭代中序遍历提前终止">迭代中序遍历（提前终止）</h3>
<p>方法一需要遍历完整棵树，即使答案在很早就已确定。我们可以利用迭代中序遍历实现提前终止，找到第k小的节点后立即返回，提升效率。</p>
<p><strong>算法思路</strong>：</p>
<ol>
<li>使用一个栈来模拟递归过程。</li>
<li>从根节点开始，将所有左子节点压入栈，直到最左边的节点。</li>
<li>弹出栈顶元素，这将是当前最小的节点。</li>
<li>每弹出一个节点，计数器k减1。当k减到0时，当前节点就是第k小的节点，直接返回。</li>
<li>如果k不为0，则转向当前节点的右子树，重复步骤2-4。</li>
</ol>
<pre><code class="language-java">public class Solution {
public int kthSmallest(TreeNode root, int k) {
Deque<TreeNode> stack = new LinkedList<>();
TreeNode current = root;
while (current != null || !stack.isEmpty()) {
// 将当前节点及其所有左子节点压入栈
while (current != null) {
stack.push(current);
current = current.left;
}
// 弹出栈顶节点，即当前最小的节点
current = stack.pop();
k--; // 计数器减1
// 如果k减到0，说明找到了第k小的节点
if (k == 0) {
return current.val;
}
// 转向右子树
current = current.right;
}
// 如果k超出节点总数，返回-1（根据题目保证k有效，此情况可不处理）
return -1;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：最坏情况O(n)（当k=n时仍需遍历大部分节点），平均情况优于O(n)，因为可能提前返回。</li>
<li><strong>空间复杂度</strong>：O(h)，其中h是树的高度。栈的深度最大为树高，在平衡BST中为O(log n)。</li>
</ul>
<h3 id="记录子节点数的递归进阶优化">记录子节点数的递归（进阶优化）</h3>
<p>如果BST结构频繁变动（插入、删除），但需要频繁查询第k小的值，前两种方法每次查询都可能需要O(n)时间。我们可以通过扩展树节点结构，记录<strong>以每个节点为根的子树中的节点个数</strong>，来优化查询效率。</p>
<p><strong>算法思路</strong>：</p>
<ol>
<li>修改树节点结构，增加一个字段（如<code>size</code>）表示以该节点为根的子树的总节点数。</li>
<li>在插入、删除节点时，维护每个节点的<code>size</code>信息。</li>
<li>查询第k小的节点时：
<ul>
<li>从根节点开始。</li>
<li>计算左子树的节点数<code>leftSize</code>。</li>
<li>如果<code>k <= leftSize</code>，说明目标节点在左子树，递归地在左子树中寻找第k小的节点。</li>
<li>如果<code>k == leftSize + 1</code>，说明当前根节点就是目标节点。</li>
<li>如果<code>k > leftSize + 1</code>，说明目标节点在右子树，递归地在右子树中寻找第<code>k - (leftSize + 1)</code>小的节点。</li>
</ul>
</li>
</ol>
<pre><code class="language-java">class TreeNodeWithSize {
int val;
TreeNodeWithSize left;
TreeNodeWithSize right;
int size; // 以该节点为根的子树包含的节点总数
TreeNodeWithSize(int x) {
val = x;
size = 1; // 初始时只有自身
}
// 假设插入操作会更新size，这里省略具体的树结构维护代码
}
public class Solution {
public int kthSmallest(TreeNodeWithSize root, int k) {
if (root == null) {
return -1;
}
// 计算左子树的节点数（如果左子树为空，则节点数为0）
int leftSize = (root.left != null) ? root.left.size : 0;
if (k <= leftSize) {
// 第k小的节点在左子树
return kthSmallest(root.left, k);
} else if (k == leftSize + 1) {
// 当前节点就是第k小的节点
return root.val;
} else {
// 第k小的节点在右子树，在右子树中寻找第 (k - (leftSize + 1)) 小的节点
return kthSmallest(root.right, k - (leftSize + 1));
}
}
}
</code></pre>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19468628
頁:
[1]