二叉搜索树的第k大节点

给定一颗二叉搜索树，找出第k大结点

  这道题也没什么好说的，就是二叉搜索树的中序遍历，找到第k大的数返回就可以了。不过需要注意的是，《剑指offer》这本书上使用C写的，所以迭代的时候，就直接使用的是k的引用，而Java中没有这种语法，所以这里我用了一个全局变量，稍微修改了一下，总之效果是一样的。

import org.junit.Test;
class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(int val){
        this.val = val;
    }
}
public class Solution{
    int kk = 0;
    public TreeNode kthNode(TreeNode root, int k){
        if (root == null || k == 0) {
            return null;
        }
        kk = k;
        return kthNodeCore(root);
    }
    private TreeNode kthNodeCore(TreeNode root){
        TreeNode target = null;
        if (root.left != null)
            target = kthNodeCore(root.left);

        if (target == null) {
            if (kk == 1) {
                // 用这种方法找到目标值，直接赋值，而不是直接迭代退栈，这里和之前用过的那些方法都不同
                target =  root;
            }
            kk--;
        }
        if (target == null && root.right != null) {
            target = kthNodeCore(root.right);
        }
        // 从这里返回找到的目标值
        return target;
    }

    @Test
    public void Test(){
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(4);

        root.right = new TreeNode(7);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(8);

        TreeNode node = kthNode(root, 8);
        // 这里是根据《剑指offer》书中的写法，直接返回结点，所以如果k大于了结点数，此时返回的是一个null
        // 这里需要判断一下。
        if (node != null)
            System.out.println(node.val);
        else
            System.out.println(-1);

    }
}

最后

以上就是漂亮帽子为你收集整理的二叉搜索树的第k大节点的全部内容，希望文章能够帮你解决二叉搜索树的第k大节点所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。