一定要早日上岸鸭 · July 24, 2021 0

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

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

/** * Definition for a binary tree node. * public 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> ls = new ArrayList<>(); // public void traverse(TreeNode root){ // if(root==null) return; // traverse(root.left); // ls.add(root.val); // traverse(root.right); // // return ls; // } // public int kthSmallest(TreeNode root, int k) { // traverse(root); // // System.out.print(ls); // return ls.get(k-1); // } // 迭代: public int kthSmallest(TreeNode root, int k) { LinkedList<TreeNode> stack = new LinkedList<>(); while(true){ while(root!=null){ stack.add(root); // System.out.print(root.val); root = root.left; } root = stack.removeLast(); if(--k==0) return root.val; root = root.right; } } }