異端開発室

二分木の根ノード root が与えられたとき、中順走査（In-order Traversal）の結果を返す。 中順走査の順序は：左部分木 → 根ノード → 右部分木 二分木ノードの定義 public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { ...

二分木の基礎知識（概念、特性、走査方法）について前回の記事で学びました。今回は主にコードの実装に焦点を当てます。 目次 二分木の疑似作成 二分木の走査 二分木のノード数の取得 二分木の葉ノード数の取得 二分木の第Kレベルのノード数の取得 二分木の高さの取得 二分木での要素検索 二分木の疑似作成 なぜ疑似作成と呼ぶのでしょうか。二分木の作成は非常に複雑なプ ...

アプローチ 共通接尾辞の再帰的な構築。（実質は有限状態オートマトン） 直接力技を使う？二分木を作れば良いが、ノードが多すぎて無理。 しかし、多くの部分木が繰り返し利用されるため、共有すれば良い。詳細はコードで確認。 実装 verify_length 関数 void verify_length(int start, int end, int left, int right) { int mid = (start + end) / 2; if (start ...

二分木の基礎理論 二分木は各ノードの子ノード数が最大2の木構造です。主要な形態として完全二分木と完全二分木が存在します。データ格納方式には配列を用いた順序格納とポインタを用いたリンク方式があります。走査方法は以下の通りです： 先行走査（深さ優先） 中間走査（深さ優先） 後行走査（深さ優先） 階層走査（幅優先） class BinaryNode: def __init__(self ...

DFS分析 深さ優先探索(DFS)は子ノードを先に訪問し、その後親ノードを訪問する手法です。訪問順序により以下の3種類に分類されます： 前順序(pre-order)：根→左→右 中順序(in-order)：左→根→右 後順序(post-order)：左→右→根 DFS非再帰実装 前順序と後順序 前順序と後順序の実装は類似したロジックで実現できます。前順序訪問は根ノードから開始し、左部分木、右 ...

一、100. 同じ木の判定 1. 問題概要 二つの二分木の根ノード p と q が与えられたとき、これらの木が同じであるかどうかを検証する関数を記述してください。 2つの木が構造的に同じで、かつノードの値が同じである場合、それらは同じであると見なされます。 2. コード class BinaryTreeChecker { public boolean areTreesIdentical(TreeNode node1, TreeNode node2) ...

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 ...