LeetCode 解题思路 22（Hot 100）

解题思路：

1. 递归思路： 传入当前节点的最小值和最大值，递归判断左右子树。
2. 结束条件： 当前节点为空或不满足二叉搜索树。

Java代码：

class Solution {public boolean isValidBST(TreeNode root) {return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);}public boolean isValidBST(TreeNode node, long lower, long upper) {if (node == null) return true;if (node.val <= lower || node.val >= upper) return false;return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);}
}

复杂度分析：

• 时间复杂度： O(n)，其中 n 是二叉树的节点数。每个节点恰好被访问一次。
• 空间复杂度： O(h)，其中 h 是二叉树的高度。空间复杂度主要由递归调用栈的深度决定，最坏情况下（树退化为链表）为O(n)，平衡树情况下为O(logn)。

解题思路：

1. 中序遍历： 先递归遍历左子树，再处理当前节点，最后遍历右子树。
2. 递减 k： 每次访问节点时，将 k 减 1。当 k 减至 0 时，当前节点即为第 k 小的元素。
3. 提前终止： 一旦找到第 k 小的元素，后续递归调用会因 k == 0 直接返回，避免多余遍历。

Java代码：

class Solution {int result, k;private void dfs(TreeNode root) {if (root == null) return;dfs(root.left);if (--k == 0) result = root.val;dfs(root.right);}public int kthSmallest(TreeNode root, int k) {this.k = k;dfs(root);return result;}
}

复杂度分析：

• 时间复杂度： O(k)，最坏情况下需要访问前 k 个节点。
• 空间复杂度： O(h)，h 为树的高度。