二叉搜索树的第K个节点

题目描述

给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。

递归解法

public class Solution {
    TreeNode res = null;
    int count;
    TreeNode KthNode(TreeNode pRoot, int k)
    {
        if(k<=0 || pRoot==null)
            return null;
        count = k;
        dfs(pRoot);
        return res;
    }
    void dfs(TreeNode pRoot)
    {
        //(1)
        if(count > 0 && pRoot.left != null){
            dfs(pRoot.left);
        }
        //(2)
        if(count==1)
            res = pRoot;
        //(3)
        if(--count > 0 && pRoot.right!=null )
           dfs(pRoot.right);
    }
}

说明

此处Count使用全局变量，而不是作为函数的参数进行传递，是因为当前面的递归调用结束时，count值可能已经发生变化。

考虑下面一颗二叉树

           5
      3       7
  2      4  6     8

中序遍历结果为 2 3 4 5 6 7 8  第3小节点值为4

递归调用过程如下：
1: (1)pRoot.val = 5 count = 3
2: (1)pRoot.val = 3 count = 3
3: (1)pRoot.val = 2 count = 3

3: (3)--count,count=2 pRoot.right==null 返回上一层
2: (3)--count,count=1 pRoot.right!=null 调用第一部分代码时count=3 第一部分代码调用结束时count=2；第三部分调用完后count=1;
4: (2)pRoot.val = 4, count = 1, res = pRoot; 找到结果。
4: (3)--count count=0 返回上一层；
2: 函数执行完 返回上一层；
1: (3) --count count= -2 返回上一层； 递归调用结束。