二分探索と自動機を用いた計算機構築
アプローチ
共通接尾辞の再帰的な構築。（実質は有限状態オートマトン）
直接力技を使う？二分木を作れば良いが、ノードが多すぎて無理。
しかし、多くの部分木が繰り返し利用されるため、共有すれば良い。詳細はコードで確認。
実装
verify_length 関数
void verify_length(int start, int end, int left, int right) {
int mid = (start + end) / 2;
if (start ...
6月12日 18:47 投稿
二分木問題の解法と実装
二分木の基礎理論
二分木は各ノードの子ノード数が最大2の木構造です。主要な形態として完全二分木と完全二分木が存在します。データ格納方式には配列を用いた順序格納とポインタを用いたリンク方式があります。走査方法は以下の通りです：
先行走査（深さ優先）
中間走査（深さ優先）
後行走査（深さ優先）
階層走査（幅優先）
class BinaryNode:
def __init__(self ...
5月28日 10:53 投稿
二分木の深さ優先探索：非再帰アルゴリズムとJava実装
DFS分析
深さ優先探索(DFS)は子ノードを先に訪問し、その後親ノードを訪問する手法です。訪問順序により以下の3種類に分類されます：
前順序(pre-order)：根→左→右
中順序(in-order)：左→根→右
後順序(post-order)：左→右→根
DFS非再帰実装
前順序と後順序
前順序と後順序の実装は類似したロジックで実現できます。前順序訪問は根ノードから開始し、左部分木、右 ...
5月24日 22:35 投稿
二分木の基本問題と解法
一、100. 同じ木の判定
1. 問題概要
二つの二分木の根ノード p と q が与えられたとき、これらの木が同じであるかどうかを検証する関数を記述してください。
2つの木が構造的に同じで、かつノードの値が同じである場合、それらは同じであると見なされます。
2. コード
class BinaryTreeChecker {
public boolean areTreesIdentical(TreeNode node1, TreeNode node2) ...
5月19日 10:29 投稿
LeetCode 二分木問題集（その2）
101 対称二分木
二分木の根ノード root が与えられたとき、木が対称構造か判定する。
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
return checkNodes(root.left, root.right);
}
private boolean checkNodes(TreeNode leftNode, TreeNode rightNode) {
if (leftNode == null ...
5月18日 15:41 投稿