题目描述
给定一棵二叉搜索树，请找出其中的第 k 小的结点。
你可以假设树和 k 都存在，并且 1 ≤ k ≤ 树的总结点数。
数据范围
树中节点数量 [1,500]
输入：root = [2, 1, 3, null, null, null, null] ，k = 3 2 / \ 1 3 输出：3
方法一：dfs O(n)
这道题可以用 dfs 来解决，题目要求找到第 k 个结点，那么我们只需要将 k 作为参数传入 dfs ，然后按照中序遍历的进行递归。
因为二叉搜索树的中序遍历结果是有序的序列，所以二叉搜索树中值最小的那个就是树中最左边的结点，也就是中序遍历结果的第一个值。
因此，要先递归到二叉搜索树的最左结点，然后每遍历到一个结点就使 k 减 1 ，再去遍历二叉树的右子树。直到 k 为 0 时，当前遍历到的结点就是第 k 大的结点即二叉搜索树的第 k 个结点。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* ans; TreeNode* kthNode(TreeNode* root, int k) { dfs(root, k); return ans; } void dfs(TreeNode* root, int& k) { if (!k || !root) return; dfs(root->left, k); k--; if (!k) ans = root; else dfs(root->right, k); } };
欢迎大家在评论区交流~
