二叉搜索树中第K小的元素

2023-12-25 11:52:13

题目链接

二叉搜索树中第K小的元素

题目描述


注意点

  • 树中的节点数为 n
  • 0 <= Node.val <= 10000

解答思路

  • 由于是二叉搜索树,特点是左子树中节点的值始终小于根节点的值,右子树的值始终大于根节点的值,所以想到使用中序遍历找到二叉搜索树中第K小的元素
  • 关键是要保存中序遍历时遍历到的节点数量,方法中的基本数据类型不会随着方法内该值的改变而进行传递,所以需要新建一个类存储节点数量,其能在中序遍历期间不断更新节点数量的值,如果某个时间遍历到某个节点时节点数量为K,则返回该节点的值作为结果

代码

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        PersonalNumber currSum = new PersonalNumber(0);
        return inorderTraversal(root, k, currSum);
    }

    public int inorderTraversal(TreeNode root, int k, PersonalNumber currSum) {
        if (root == null) {
            return -1;
        }
        // 中序遍历,左子树->根节点->右子树
        int leftRes = inorderTraversal(root.left, k, currSum);
        if (leftRes != -1) {
            return leftRes;
        }
        // 访问到一个节点节点数目 + 1
        currSum.add(1);
        if (currSum.val == k) {
            return root.val;
        }
        int rightRes = inorderTraversal(root.right, k, currSum);
        if (rightRes != -1) {
            return rightRes;
        }
        return -1;
    }   
}

class PersonalNumber {
    public int val;
    public PersonalNumber(){}
    public PersonalNumber(int val) {
        this.val = val;
    }
    public void add(int addNum) {
        val = val + addNum;
    }
}

关键点

  • 中序遍历的思想

文章来源:https://blog.csdn.net/weixin_51628158/article/details/135193521
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。