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

题目链接

二叉搜索树中第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;
    }
}

关键点

• 中序遍历的思想