LeetCode 230 Kth Smallest Element in a BST

标签: 二叉搜索树 LeetCode 发布于:2022-02-07 09:49:48 编辑于:2022-02-07 09:49:48 浏览量:361

概述

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

未经允许,禁止转载,本文源站链接:https://iamazing.cn/