给定一棵二叉搜索树,请找出其中的第k大的结点。
如果按照中序遍历的顺序遍历一棵二叉搜索树,遍历序列的数值是递增排序的。只需要用中序遍历算法遍历一棵二叉搜索树,就很容易找出它的第k大结点。
public class Test { private static class BinaryTreeNode { private int val; private BinaryTreeNode left; private BinaryTreeNode right; public BinaryTreeNode() { } public BinaryTreeNode(int val) { this.val = val; } @Override public String toString() { return val + ""; } } public static BinaryTreeNode kthNode(BinaryTreeNode root, int k) { if (root == null || k < 1) { return null; } int[] tmp = {k}; return kthNodeCore(root, tmp); } private static BinaryTreeNode kthNodeCore(BinaryTreeNode root, int[] k) { BinaryTreeNode result = null; // 先成左子树中找 if (root.left != null) { result = kthNodeCore(root.left, k); } // 如果在左子树中没有找到 if (result == null) { // 说明当前的根结点是所要找的结点 if(k[0] == 1) { result = root; } else { // 当前的根结点不是要找的结点,但是已经找过了,所以计数器减一 k[0]--; } } // 根结点以及根结点的左子树都没有找到,则找其右子树 if (result == null && root.right != null) { result = kthNodeCore(root.right, k); } return result; } }
Copyright© 2013-2020
All Rights Reserved 京ICP备2023019179号-8