leetcode算法之面试题【54】二叉搜索树的第k大节点

我会带着你远行 2023-02-18 14:05 11阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：递归
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

给定一棵二叉搜索树，请找出其中第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 ≤ 二叉搜索树元素个数

#### 方案：递归 ####

*  采用想减法，从最右值开始找起，到k–到1那个数，就是第k大的

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    class Solution { 
        int tmpk;
        int val=-1;
        public int kthLargest(TreeNode root, int k) { 
            tmpk = k;
            findnode(root);
            return val;
        }
        public void findnode(TreeNode node){ 
            if(node.right!=null) findnode(node.right);
            if(tmpk==1&&val==-1) { val=node.val;return;}
            if(tmpk>1) { 
                tmpk--;
                if(node.left!=null) findnode(node.left);
            }
        }
    }

##### 复杂度计算 #####

*  时间复杂度：O(n)
 *  空间复杂度：O(1)

[Git]: https://github.com/ch98road/leetcode