Skip to content
Branch: master
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
README.md
tree.cpp

README.md

Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note: You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

Follow up: What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

Hint:

  • Try to utilize the property of a BST.
  • What if you could modify the BST node's structure?
  • The optimal runtime complexity is O(height of BST).

Credits: Special thanks to @ts for adding this problem and creating all test cases.

Solution

中序遍历,更新k值,访问时k--, 若此时k == 0, 则当前值即为结果

public:
	int kthSmallest(TreeNode *root, int k) {
		int result;
		/*
		if (root == nullptr) {
			return 0;
		}
		*/
		kthSmallest(root, k, result);
		return result;
	}
private:
	/* k为需要查找的第k小的数, result为结果,返回true表示已经查找到
	 * 注意k为引用类型,否则k的值更新不能反馈到上一栈调用
	*/
	bool kthSmallest(TreeNode *root, int &k, int &result) {
		if (root->left) {
			if (kthSmallest(root->left, k, result)) {
				return true;
			}
		}
		k -= 1;
		if (k == 0) {
			result = root->val;
			return true;
		}
		if (root->right) {
			if (kthSmallest(root->right, k, result)) {
				return true;
			}
		}
		return false;
	}
};

优化

如果允许修改树结构,保存节点左孩子个数,是否可以优化呢?

You can’t perform that action at this time.