本题其实难度并不高,我也看出了解题思路,就是用树的inorder traversal,但是细节处理上出了问题。
关键点就是设置一个全局变量count
,来追踪target
,每遇到一个node
,就自减1即可,本题可说的并不多,直接看代码会更清晰
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private static int count;
private static TreeNode target;
public int kthSmallest(TreeNode root, int k) {
count = k;
inorder(root);
return target.val;
}
private void inorder(TreeNode node) {
if (node.left != null) {
inorder(node.left);
}
--count;
if (count == 0) {
target = node;
}
if (node.right != null) {
inorder(node.right);
}
}
}