Description：

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.

题意：从二叉查找树中找第k小的数。

思路：中序遍历，找到第k个便是。

C++：

class Solution {public:    int num=0;//记录次数int re;//记录最终结果//中序遍历的方法void digui(TreeNode* root, int k){    if(root->left!=NULL)        digui(root->left,k);    num++;    if(num==k)        re=root->val;    if(root->right!=NULL)        digui(root->right,k);    return;}    int kthSmallest(TreeNode* root, int k) {        digui(root,k);    return re;    }};

LeetCode很奇怪，同样的代码Java却过不了。。。还是1 null 2 ，2这个数据过不了，我自己测试的都能过。。。。

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */public class Solution {    public static int cnt = 0;    public static int ans;    public int kthSmallest(TreeNode root, int k) {        travels(root, k);        return ans;    }    public void travels(TreeNode node, int k) {        if(node.left != null)            travels(node.left, k);        cnt ++;        if(cnt == k) {            ans = node.val;        }        if(node.right != null)            travels(node.right, k);    }}

更新----------------

终于找到原因了，原来我用了静态变量，后台测试连续调用，结果不清零。。。

最终Java代码：

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */public class Solution {    public int cnt = 0;    public int ans;    public int kthSmallest(TreeNode root, int k) {        travels(root, k);        return ans;    }    public void travels(TreeNode node, int k) {        if(node == null)            return ;        travels(node.left, k);        cnt ++;        if(cnt == k) {            ans = node.val;            return ;        }        travels(node.right, k);    }}