[剑指offer]二叉搜索树中的第k小的节点

很简单的题，中序递归或者遍历。

    TreeNode KthNode(TreeNode root, int k)
    {
    	Stack<TreeNode> st = new Stack<>();
    	TreeNode cur = root;
    	
    	while(cur != null || !st.isEmpty()){
    		while(cur != null){
    			st.push(cur);
    			cur = cur.left;
    		}
    		
    		if(!st.isEmpty()){
    			cur = st.pop();
    			
    			k--;
    			if(k == 0) return cur;
    			
    			cur = cur.right;
    		}
    	}
    	//k!= 0 not found
    	return null;
    }

递归解法需要定义外部变量计数就行了，也可以把外部计数和ans和参数带着，但是为了省去栈操作的开销还是不带了吧。

	int c = 0;
	TreeNode ans = null;

	private void f(TreeNode root) {
		if (c != 0) {
			if (root.left != null)
				f(root.left);
			c--;
			if (c == 0)
				ans = root;
			if (root.right != null)
				f(root.right);
		}
	}

	TreeNode KthNode(TreeNode root, int k) {
		if(root==null)return root;
		c = k;
		f(root);
		return ans;
	}