マツシタのお勉強

Binary Search Tree

Binary Search Tree Iterator in LeetCode

問題 Binary Search Treeにおけるイテレータを実装する問題。next()メソッドで取得できる値は現時点での最小値となる。 Binary Search Tree Iterator - LeetCode ソースコード

2分探索木からノードを削除する Delete Node in a BST in LeetCode

問題 2分探索木とint型のkeyが与えられる。BSTからkeyの要素を削除する問題。 leetcode.com 解法 以下のステップで解く 2分探索でkeyを見つける 削除するノードの右側のサブツリーの最小値を持つノードを削除するノードに置き換える。 右側のサブツリーから…

Find the location of the given string from a sorted array of string which is interspersed with empty strings

Problem Given a sorted array of strings which is interspersed with empty strings, write a method to find the location of a given string EXAMPLE Input: find “ball” in {“at”, “”, “”, "ball”, "”, "”, "car”,“”, "”, "dad”, ”“, ”“} Output:4 Solu…

Find the next node (in-oder traversal) of a given node in a binary search tree

Problem Write an algorithm to find the next node (i.e., in-oder successor) of a given node in a binary search tree. You may assume that each node has a link to its parent. Solution This problem can be solved by thinking the two patterns. F…

Check if a binary tree is a binary search tree

Problem Implement a function to check if a binary tree is a binary search tree Solution There are some solutions to solve this problem. I’ll introduce the all solution which includes I came up with. First Solution is using a range (min, ma…

Make a Binary Search Tree from sorted array

Problem Given a sorted (increasing order) array with unique integer elements, write an algorithm to create a binary search tree with minimal height. How to Solve This problem asks me to create a BST (Binary Search Tree) from array. What is…