leetCode の「Kth Smallest Element in a BST」を解いた。
https://leetcode.com/problems/kth-smallest-element-in-a-bst/
この問題は、引数で与えられたバイナリーツリーの中で k 番目に小さい数を戻り値として返すメソッドを作成するというもの。
提出したコードは以下。ロジックの本体部分である traverseInOrder() では、In orderで ツリーを辿って、小さい方から k 番目まで辿れたらそれで充分なので、return している。
public int kthSmallest(TreeNode root, int k) { List<Integer> list = new ArrayList<>(); traverseInOrder(root, list, k); return list.get(k - 1); } private void traverseInOrder(TreeNode node, List list, int k) { // これ以上、ツリーを辿る必要なし。 if (list.size() >= k) { return; } // 左側から辿る if (node.left != null) { traverseInOrder(node.left, list, k); } // 当該Nodeの値を確保 list.add(node.val); // 最後に右側を辿る if (node.right != null) { traverseInOrder(node.right, list, k); } }
提出結果は以下となった。
Runtime: 0 ms, faster than 100.00% of Java online submissions for Kth Smallest Element in a BST. Memory Usage: 41.1 MB, less than 5.51% of Java online submissions for Kth Smallest Element in a BST.
速度は十分なので、これで良しとする。