1.思路
中序周遊可以得到遞增的序列,是以尋求第k大的數,就用中序周遊的倒序(即先周遊右子樹,再根節點,最後左子樹)
2.代碼
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private int k,res;
public int kthLargest(TreeNode root, int k) {
this.k=k;
dfs(root);
return res;
}
private void dfs(TreeNode root){
if(root==null)
return;
dfs(root.right);
if(k==0)
return;
k=k-1;
if(k==0){//目前是第K大的數
res=root.val;//記錄結果
return;
}
dfs(root.left);
}
}
3.複雜度
當樹退化為連結清單時,時間複雜度、空間複雜度均為O(N)