【剑指offer】面试题54：二叉搜索树的第k大节点

港控/mmm° 2022-06-11 06:49 89阅读 0赞

## 题目 ##

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

## 思路 ##

二叉搜索树：左子节点 <= 根节点 <= 右子节点  
中序遍历：左 -> 根 -> 右

## 代码 ##

/**
     * 给定一颗二叉搜索树，请找出其中的第k大的结点。
     * 例如， 5 / \ 3 7 /\ /\ 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。
     * 
     * @author peige
     */
    public class _54_KthNodeInBST {
        
    
        public static class TreeNode {
        
            public int val = 0;
            public TreeNode left = null;
            public TreeNode right = null;
            public TreeNode(int val) {
                this.val = val;
            }
        }
    
        private int kth = 0;
    
        public TreeNode KthNode(TreeNode pRoot, int k) {
            if(pRoot == null || k <= 0)
                return null;
            TreeNode result = KthNode(pRoot.left, k);
            if(kth == k)
                return result;
            if(++kth == k)
                return pRoot;
            result = KthNode(pRoot.right, k);
            return result;
        }
    }

## 测试 ##

public class _54_Test {
    
        public static void main(String[] args) {
            test1();
            test2();
            test3();
        }
    
        /**
         *        8
         *      /   \
         *     6    12
         *    / \   / \
         *   3  7  10 14
         */
        private static void test1() {
            TreeNode node1 = new TreeNode(8);
            TreeNode node2 = new TreeNode(6);
            TreeNode node3 = new TreeNode(12);
            TreeNode node4 = new TreeNode(3);
            TreeNode node5 = new TreeNode(7);
            TreeNode node6 = new TreeNode(10);
            TreeNode node7 = new TreeNode(14);
            node1.left = node2;
            node1.right = node3;
            node2.left = node4;
            node2.right = node5;
            node3.left = node6;
            node3.right = node7;
    
            _54_KthNodeInBST knib = new _54_KthNodeInBST();
            TreeNode n = knib.KthNode(node1, 3);
            System.out.println(n == node5);
    
            _54_KthNodeInBST knib2 = new _54_KthNodeInBST();
            n = knib2.KthNode(node1, 4);
            System.out.println(n == node1);
    
            _54_KthNodeInBST knib3 = new _54_KthNodeInBST();
            n = knib3.KthNode(node1, 1);
            System.out.println(n == node4);
    
            _54_KthNodeInBST knib4 = new _54_KthNodeInBST();
            n = knib4.KthNode(node1, 7);
            System.out.println(n == node7);
    
            _54_KthNodeInBST knib5 = new _54_KthNodeInBST();
            n = knib5.KthNode(node1, 8);
            System.out.println(n);
    
            _54_KthNodeInBST knib6 = new _54_KthNodeInBST();
            n = knib6.KthNode(node1, 0);
            System.out.println(n);
        }
    
        private static void test2() {
            TreeNode node1 = new TreeNode(1);
            _54_KthNodeInBST knib = new _54_KthNodeInBST();
            TreeNode n = knib.KthNode(node1, 1);
            System.out.println(node1 == n);
        }
    
        private static void test3() {
            _54_KthNodeInBST knib = new _54_KthNodeInBST();
            TreeNode n = knib.KthNode(null, 1);
            System.out.println(n);
        }
    }