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;
    }
};