面试题54：二叉搜索树的第k大节点

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

思路：中序遍历二叉树，第k个即为第k大的节点。注意全局变量ans和count的设置。

代码实现：

package Question54;

public class T01 {

    static int ans, count;

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);

        node2.leftChild = node1;
        node2.rightChild = node3;
        node3.leftChild = node4;
        node3.rightChild = node5;

        System.out.println(solve(node2, 2));
    }

    public static int solve(TreeNode root, int k) {
        help(root, k);
        return ans;
    }

    public static void help(TreeNode root, int k) {
        if(root != null) {
            if(root.rightChild != null) help(root.rightChild, k);
            if(++count == k) {
                ans = root.val;
                return ;
            }
            if(root.leftChild != null) help(root.leftChild, k);
        }
    }
}

class TreeNode{

    int val;
    TreeNode leftChild;
    TreeNode rightChild;

    public TreeNode(int val) {
        this.val = val;
    }
}