LeetCode 230. 二叉搜索树中第K小的元素

ゞ浴缸里的玫瑰 2022-10-25 12:57 142阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]  
[官方题解][Link 1]

//解法一:利用中序遍历将值存储在数组里
    class Solution {
        
      public ArrayList<Integer> inorder(TreeNode root, ArrayList<Integer> arr) {
        
        if (root == null) return arr;
        inorder(root.left, arr);
        arr.add(root.val);
        inorder(root.right, arr);
        return arr;
      }
    
      public int kthSmallest(TreeNode root, int k) {
        
        ArrayList<Integer> nums = inorder(root, new ArrayList<Integer>());
        return nums.get(k - 1);
      }
    }

//解法二：在栈的帮助下，可以将方法一的递归转换为迭代，这样可以加快速度，因为这样可以不用遍历整个树，可以在找到答案后停止。
    class Solution {
        
      public int kthSmallest(TreeNode root, int k) {
        
        LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
    
        while (true) {
        
          while (root != null) {
        
            stack.add(root);
            root = root.left;
          }
          root = stack.removeLast();
          if (--k == 0) return root.val;
          root = root.right;
        }
      }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]: /images/20221024/9637cee5e5db4c9db866dc469bbbc45e.png
[Link 1]: https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/solution/er-cha-sou-suo-shu-zhong-di-kxiao-de-yuan-su-by-le/