题目描述

给定一颗二叉搜索树，请找出其中的第k大的结点。

思路

1.中序遍历二叉搜索树
2.递归调用

代码1

Common.TreeNode KthNodeII(Common.TreeNode pRoot, int k) {
        if (pRoot == null || k < 0)
            return null;
        Stack<Common.TreeNode> stack = new Stack<>();
        Common.TreeNode node = pRoot;
        int count = 0;
        while (node != null || !stack.isEmpty()) {
            while (node!= null) {
                stack.push(node);
                node = node.left;
            }//左子树为空或已经被访问
            if (!stack.isEmpty()) {
                node=stack.pop();//访问根节点
                count++;
                if (count == k)
                    return node;
                node = node.right;//处理右子树
            }
        }
        return null;
    }

代码2

Common.TreeNode KthNode(Common.TreeNode pRoot, int k) {
        if (pRoot == null || k < 0)
            return null;
        Common.TreeNode res;
        if ((res = KthNode(pRoot.left, k)) != null)//左子树找到，则返回
            return res;
        count++;//访问过左子树，count+1
        if (k == count)//如果相等，说明当前节点就是要找的第k个节点
            return pRoot;
        res = KthNode(pRoot.right, k);//如果还没找到，查找右子树
        if (res != null)
            return res;
        return null;
    }