剑指offer-62、⼆叉搜索树的第k个结点

题⽬描述给定⼀棵⼆叉搜索树请找出其中的第 k ⼩的 TreeNode 结点。示例1输⼊{5,3,7,2,4,6,8},3返回值{4}思路及解答二叉搜索树的关键性质二叉搜索树具有一个重要特性中序遍历左-根-右BST会得到一个升序排列的节点值序列。因此寻找第k小的节点本质上就是获取中序遍历序列中的第k个元素。理解这一点是掌握所有解法的基石。递归中序遍历直观版算法思路进行递归中序遍历将遍历到的节点值依次加入一个列表。遍历完成后列表中的元素就是升序排列的。从列表中取出第k-1个元素索引从0开始即为答案。javaclass TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val x; } } public class Solution { public int kthSmallest(TreeNode root, int k) { // 用于存储中序遍历结果的列表 ListInteger inorderList new ArrayList(); // 执行中序遍历 inorderTraversal(root, inorderList); // 返回第k小的元素列表索引从0开始所以是k-1 return inorderList.get(k - 1); } /** * 递归中序遍历二叉树 * param node 当前遍历的节点 * param list 存储遍历结果的列表 */ private void inorderTraversal(TreeNode node, ListInteger list) { if (node null) { return; // 递归终止条件遇到空节点则返回 } inorderTraversal(node.left, list); // 递归遍历左子树 list.add(node.val); // 访问当前节点将值加入列表 inorderTraversal(node.right, list); // 递归遍历右子树 } }时间复杂度O(n)。需要遍历树中的所有n个节点。空间复杂度O(n)。主要取决于递归调用栈的深度最坏情况为O(n)树退化成链表和存储遍历结果的列表O(n)。迭代中序遍历提前终止方法一需要遍历完整棵树即使答案在很早就已确定。我们可以利用迭代中序遍历实现提前终止找到第k小的节点后立即返回提升效率。算法思路使用一个栈来模拟递归过程。从根节点开始将所有左子节点压入栈直到最左边的节点。弹出栈顶元素这将是当前最小的节点。每弹出一个节点计数器k减1。当k减到0时当前节点就是第k小的节点直接返回。如果k不为0则转向当前节点的右子树重复步骤2-4。javapublic class Solution { public int kthSmallest(TreeNode root, int k) { DequeTreeNode 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; } }时间复杂度最坏情况O(n)当kn时仍需遍历大部分节点平均情况优于O(n)因为可能提前返回。空间复杂度O(h)其中h是树的高度。栈的深度最大为树高在平衡BST中为O(log n)。记录子节点数的递归进阶优化如果BST结构频繁变动插入、删除但需要频繁查询第k小的值前两种方法每次查询都可能需要O(n)时间。我们可以通过扩展树节点结构记录以每个节点为根的子树中的节点个数来优化查询效率。算法思路修改树节点结构增加一个字段如size表示以该节点为根的子树的总节点数。在插入、删除节点时维护每个节点的size信息。查询第k小的节点时从根节点开始。计算左子树的节点数leftSize。如果k leftSize说明目标节点在左子树递归地在左子树中寻找第k小的节点。如果k leftSize 1说明当前根节点就是目标节点。如果k leftSize 1说明目标节点在右子树递归地在右子树中寻找第k - (leftSize 1)小的节点。javaclass 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)); }