二分探索木（BST）は、左部分木のすべてのノードが根より小さく、右部分木のすべてのノードが根より大きいという性質を持つ。この構造により、中間順走査（in-order traversal）を行うと昇順の列が得られる。この特性を活用することで、多くの問題を効率的に解くことができる。
最小絶対差（LeetCode 530）
BSTの中間順走査により昇順列を得られることを利用し、隣接要素間の差の最小値を計算する。再帰中に直前のノード値を保持し、現在のノードとの差を更新していく。
class Solution {
private int minDiff = Integer.MAX_VALUE;
private Integer lastVal = null;
public int getMinimumDifference(TreeNode root) {
traverse(root);
return minDiff;
}
private void traverse(TreeNode node) {
if (node == null) return;
traverse(node.left);
if (lastVal != null) {
minDiff = Math.min(minDiff, node.val - lastVal);
}
lastVal = node.val;
traverse(node.right);
}
}配列表現による二分木
完全二分木は配列で効率的に表現できる。インデックス i のノードについて、左子は 2*i+1、右子は 2*i+2、親は (i-1)/2 となる。これにより、メモリ効率良く木を操作可能。
class ArrayBinaryTree {
private final List<Integer> data;
public ArrayBinaryTree(List<Integer> arr) {
this.data = new ArrayList<>(arr);
}
public Integer getValue(int idx) {
if (idx < 0 || idx >= data.size()) return null;
return data.get(idx);
}
public int leftChild(int idx) { return 2 * idx + 1; }
public int rightChild(int idx) { return 2 * idx + 2; }
public int parent(int idx) { return (idx - 1) / 2; }
public List<Integer> inorder() {
List<Integer> result = new ArrayList<>();
dfs(0, "in", result);
return result;
}
private void dfs(int idx, String mode, List<Integer> res) {
if (getValue(idx) == null) return;
if ("pre".equals(mode)) res.add(getValue(idx));
dfs(leftChild(idx), mode, res);
if ("in".equals(mode)) res.add(getValue(idx));
dfs(rightChild(idx), mode, res);
if ("post".equals(mode)) res.add(getValue(idx));
}
}K番目に小さい要素（LeetCode 230）
中間順走査で昇順にアクセスできるため、カウンタを用いてK番目の要素を取得。見つかった時点で早期終了。
class Solution {
private int target;
private int count = 0;
private int result = -1;
public int kthSmallest(TreeNode root, int k) {
target = k;
inorder(root);
return result;
}
private void inorder(TreeNode node) {
if (node == null || result != -1) return;
inorder(node.left);
if (++count == target) {
result = node.val;
return;
}
inorder(node.right);
}
}BSTの検証（LeetCode 98）
中間順走査で得られる列が真に単調増加であるかを確認。直前の値と比較し、違反があれば無効と判定。
class Solution {
private Integer prev = null;
private boolean valid = true;
public boolean isValidBST(TreeNode root) {
check(root);
return valid;
}
private void check(TreeNode node) {
if (node == null || !valid) return;
check(node.left);
if (prev != null && prev >= node.val) {
valid = false;
return;
}
prev = node.val;
check(node.right);
}
}走査結果からの木の再構築
先行順（pre-order）と中間順（in-order）から木を再構築する際、先行順の先頭が根であり、中間順でその位置を基に左右部分木を分割。ハッシュマップでインデックスを高速検索。
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
Map<Integer, Integer> indexMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
indexMap.put(inorder[i], i);
}
return build(preorder, 0, preorder.length, inorder, 0, inorder.length, indexMap);
}
private TreeNode build(int[] pre, int pL, int pR, int[] in, int iL, int iR, Map<Integer, Integer> map) {
if (pL == pR) return null;
int rootVal = pre[pL];
TreeNode root = new TreeNode(rootVal);
int rootIdx = map.get(rootVal);
int leftSize = rootIdx - iL;
root.left = build(pre, pL + 1, pL + 1 + leftSize, in, iL, rootIdx, map);
root.right = build(pre, pL + 1 + leftSize, pR, in, rootIdx + 1, iR, map);
return root;
}
}区間表現のベストプラクティス：左閉右開
再帰的処理では [start, end) 表記が推奨される。理由：
- 空区間の判定が
start == endで統一可能 - 要素数が
end - startで直感的 - Java/C++/Pythonの標準ライブラリと整合性あり
- 境界値エラー（off-by-one）を低減
レベル順接続（LeetCode 117）
キューを用いたレベル順走査で、各レベルのノードを順に接続。末尾ノードの next は null。
class Solution {
public Node connect(Node root) {
if (root == null) return null;
Queue<Node> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
Node prev = q.poll();
enqueueChildren(prev, q);
for (int i = 1; i < size; i++) {
Node curr = q.poll();
enqueueChildren(curr, q);
prev.next = curr;
prev = curr;
}
prev.next = null;
}
return root;
}
private void enqueueChildren(Node node, Queue<Node> q) {
if (node.left != null) q.offer(node.left);
if (node.right != null) q.offer(node.right);
}
}リストへの展開（LeetCode 114）
先行順でノードを収集し、右リンクのみで連結。空間最適化版では、スタックまたはMorris traversal風のin-place変換も可能。
class Solution {
public void flatten(TreeNode root) {
Deque<TreeNode> stack = new LinkedList<>();
if (root != null) stack.push(root);
TreeNode prev = null;
while (!stack.isEmpty()) {
TreeNode curr = stack.pop();
if (prev != null) {
prev.left = null;
prev.right = curr;
}
if (curr.right != null) stack.push(curr.right);
if (curr.left != null) stack.push(curr.left);
prev = curr;
}
}
}BSTイテレータ（LeetCode 173）
中間順走査を遅延評価で実現。スタックに左パスを事前ロードし、next() 呼び出し時に右部分木を探索。
class BSTIterator {
private final Deque<TreeNode> stack = new ArrayDeque<>();
public BSTIterator(TreeNode root) {
pushLeft(root);
}
public int next() {
TreeNode node = stack.pop();
pushLeft(node.right);
return node.val;
}
public boolean hasNext() {
return !stack.isEmpty();
}
private void pushLeft(TreeNode node) {
while (node != null) {
stack.push(node);
node = node.left;
}
}
}最近共通祖先（LeetCode 236）
後行順走査で、左右部分木に目的ノードが含まれるかをチェック。両方に含まれれば現在ノードがLCA。片方にのみ含まれる場合はその結果を伝播。
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) return root;
return left != null ? left : right;
}
}ソート済み配列からBST生成（LeetCode 108）
中央要素を根とし、左右部分を再帰的に処理。バランスの取れたBSTが自然に構築される。
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return build(nums, 0, nums.length);
}
private TreeNode build(int[] arr, int l, int r) {
if (l >= r) return null;
int mid = l + (r - l) / 2;
TreeNode root = new TreeNode(arr[mid]);
root.left = build(arr, l, mid);
root.right = build(arr, mid + 1, r);
return root;
}
}