leetcode 剑指 Offer 54. 二叉搜索树的第k大节点

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

示例 1:

示例 2:

限制：

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

解法一：

按右根左的顺序递归遍历二叉搜索树，第k个结点，即使第k大的结点

 1 class Solution {
 2     public int kth = 0;
 3     public int k = 0;
 4     // 递归中序遍历,右根左，第k个结点，即使第k大的结点
 5     public int kthLargest(TreeNode root, int k) {
 6         this.k = k;
 7         midTravesal(root);
 8         return kth;
 9     }
10 
11     public void midTravesal(TreeNode root){
12 
13         if(root != null){
14             midTravesal(root.right);
15             k--;
16             if(k == 0){
17                 kth = root.val;
18                 return;
19             }   
20             midTravesal(root.left);
21         }
22     }
23 }

leetcode运行时间为0ms, 空间为38.8mb

复杂度分析：

时间复杂度：遍历了树的k个结点，所以时间复杂度为O(k)

空间复杂度：递归栈的深度就是空间复杂度，二叉搜索树的最大深度为O(n), 最小深度为O(logn)

解法二：

利用栈的方式实现非递归访问栈，同样访问的第k个结点是我们的目标结点

 1 class Solution {
 2 
 3     // 利用栈实现中序遍历,右根左，第k个结点，即使第k大的结点
 4     public int kthLargest(TreeNode root, int k) {
 5         Stack<TreeNode> stack = new Stack<TreeNode>();
 6         TreeNode top = root;
 7         while(!stack.isEmpty() || top != null){
 8             while(top != null){
 9                 stack.push(top);
10                 top = top.right;
11             }
12             top = stack.pop();
13             k--;
14             if(k == 0){
15                 return top.val;
16             }
17             top = top.left;
18         }
19         return 0;
20     }
21 }

leetcode运行时间为1ms, 空间为38.5mb

复杂度分析：

时间复杂度：遍历了树的k个结点，所以时间复杂度为O(k)

空间复杂度：栈的大小就是空间复杂度，所以同样是O(k)