LeetCode 230 Kth Smallest Element in a BST
概述
https://leetcode.com/problems/kth-smallest-element-in-a-bst/
直接法
中序遍历一遍，得到升序的列表，求出第 k 个即可。
递归法
实际上没有必要遍历一遍，遍历过程中计算一下序号即可。
对于一个节点的序号，计算公式为：父节点的序号 + 左子节点的元素个数 + 1
class Solution {
public:
bool found = false;
int k;
int ans;
int kthSmallest(TreeNode* root, int k) {
this->k = k;
helper(root, 0);
return ans;
}
int helper(TreeNode* root, int n) {
if (found) return -1;
if (!root) return 0;
int lcount = helper(root->left, n);
if (!found && n + lcount + 1 == k) {
found = true;
ans = root->val;
}
int rcount = helper(root->right, n + lcount + 1);
return lcount + 1 + rcount;
}
};