leetcode 230. Kth Smallest Element in a BST | 230. 二叉搜索树中第K小的元素（Java）

墨蓝 2022-10-09 02:50 116阅读 0赞

## 题目 ##

[https://leetcode.com/problems/kth-smallest-element-in-a-bst/][https_leetcode.com_problems_kth-smallest-element-in-a-bst]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

#### 方法1：中序遍历+剪枝 ####

import java.util.ArrayList;
    import java.util.List;
    
    class TreeNode { 
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() { }
        TreeNode(int val) {  this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) { 
          this.val = val;
          this.left = left;
          this.right = right;
        }
    }
    
    class Solution { 
        List<Integer> list;
        int k;
    
        public int kthSmallest(TreeNode root, int k) { 
            list = new ArrayList<>();
            this.k = k;
            inOrder(root);
            return list.get(k - 1);
        }
    
        public void inOrder(TreeNode node) { 
            if (node == null) return;
            inOrder(node.left);
            list.add(node.val);
            if (list.size() >= k) return; // 剪枝，及时停止，不需要走完整棵树
            inOrder(node.right);
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

#### 方法2：Iterative Inorder Traversal ####

参考：[https://leetcode.com/problems/kth-smallest-element-in-a-bst/solution/][https_leetcode.com_problems_kth-smallest-element-in-a-bst_solution]  
The above recursion could be converted into iteration, with the help of **stack**. This way one could speed up the solution because there is no need to build the entire inorder traversal, and one could stop after the kth element.  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 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_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 2]

[https_leetcode.com_problems_kth-smallest-element-in-a-bst]: https://leetcode.com/problems/kth-smallest-element-in-a-bst/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221005/0beeb5994f264b1ba9d17b825cae63fa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20221005/53872f6c5b2c4471a6ebebc73e87fd9d.png
[https_leetcode.com_problems_kth-smallest-element-in-a-bst_solution]: https://leetcode.com/problems/kth-smallest-element-in-a-bst/solution/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]: /images/20221005/e943c7b22a1643d7ba172aff780f9fc5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 2]: /images/20221005/d9f8261637e3417d8b28aecc542f3226.png