**剑指offer--54. 二叉搜索树的第K大节点

Love The Way You Lie 2023-02-21 12:40 14阅读 0赞

## 题目描述 ##

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

**示例 1:**

输入: root = \[3,1,4,null,2\], k = 1  
3  
/  
1 4  
  
2  
输出: 4

**示例 2:**

输入: root = \[5,3,6,2,4,null,null,1\], k = 3  
5  
/  
3 6  
/  
2 4  
/  
1  
输出: 4

**限制：**

1 ≤ k ≤ 二叉搜索树元素个数

## 思路：二叉搜索树的中序遍历是递增序列、递归 ##

递归思路：

1.  终止条件：root为空时，直接返回
2.  递归右子树
3.  统计序号k=k-1(k减到0)；记录结果当k=0时找到第k大节点，记录res = root.val并返回
4.  递归左子树

## 解决方法 ##

二叉搜索树的中序遍历（左、中、右）是递增序列；  
则（右、中、左）就是递减序列，找出递减序列的第k个值就是二叉搜索树的第K大节点

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        int res, count;  //创建全局变量
        public int kthLargest(TreeNode root, int k) {
        
            this.count = k; //利用形参值k对类变量count进行初始化
            dfs(root);  //使用类变量，递归
            return res;
        }
        public void dfs(TreeNode root){
        
            if(root == null)
                return;
            dfs(root.right);
            if(--count == 0){
        
                res = root.val;
                return;
            }
            dfs(root.left);
        }
    }

利用list集合来保存（右、中、左）遍历的结果，获取数组中第k-1个节点就是二叉搜索树的第k大节点  
使用list集合的实现类`ArrayList`来保存`（需要了解LinkedList和ArrayList的区别）`

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public int kthLargest(TreeNode root, int k) {
        
            List<Integer> list = new ArrayList<>();  //利用list来保存遍历的结果，需要创建list
            bfs(root, list);
            return list.get(k-1);
        }
        public List<Integer> bfs(TreeNode root, List<Integer> list){
        
            if(root == null) return list;
            bfs(root.right, list); //递归右子树
            list.add(root.val); //保存节点的值，加入list
            bfs(root.left, list); //递归左子树
            return list;
        }  
    }