我的LeetCode：https://leetcode-cn.com/u/ituring/
我的LeetCode刷題原始碼[GitHub]：https://github.com/izhoujie/Algorithmcii
LeetCode 面試題54. 二叉搜索樹的第k大節點
題目
給定一棵二叉搜索樹，請找出其中第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 ≤ 二叉搜索樹元素個數
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
解題思路
思路1-中序遍歷記錄排序序號回傳
二叉搜索樹的中序遍歷結果是有序序列：
- 左根右的中序遍歷獲得的是遞增序列；
- 右根左的中序遍歷獲得的是遞減序列；
所以，可以對二叉搜索樹進行右根左的中序遍歷并記錄遍歷的序號，回傳遍歷到的第k個節點值即可；
演算法復雜度:
- 時間復雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $
- 空間復雜度： $ {\color{Magenta}{\Omicron\left(1\right)}} $
演算法原始碼示例
package leetcode;
/**
* @author ZhouJie
* @date 2020年5月17日 上午1:15:08
* @Description: 面試題54. 二叉搜索樹的第k大節點
*
*/
public class LeetCode_Offer_54 {
}
// Definition for a binary tree node.
class TreeNode_Offer_54 {
int val;
TreeNode_Offer_54 left;
TreeNode_Offer_54 right;
TreeNode_Offer_54(int x) {
val = x;
}
}
class Solution_Offer_54 {
/**
* @author: ZhouJie
* @date: 2020年5月17日 上午1:16:10
* @param: @param root
* @param: @param k
* @param: @return
* @return: int
* @Description: 1-中序遍歷，左根右為遞增可求第k小，右根左為遞減可求第k大；
*
*/
// count記錄排序序號
int rst = 0, count = 0;
public int kthLargest_1(TreeNode_Offer_54 root, int k) {
dfs(root, k);
return rst;
}
private void dfs(TreeNode_Offer_54 root, int k) {
if (root == null) {
return;
} else {
dfs(root.right, k);
// count為k時即找到了第k大的數
if (++count == k) {
rst = root.val;
return;
}
dfs(root.left, k);
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/189841.html
標籤：Java