ツリーの再構築(面接アルゴリズム)
タイトルの説明:
ツリーの前順および中順の結果を入力し、ツリーを再構築します.入力された前シーケンスおよび中シーケンスの結果に重複する数値が含まれていないと仮定します.例えば、前シーケンス遍歴シーケンス{1,2,4,7,3,5,6,8}と中シーケンス遍歴シーケンス{4,7,2,1,5,3,8,6}を入力すると、ツリーが再構築され、戻ります.
ツリーの遍歴方法:
前順のループ:ルートノード->左サブツリー(または左ノード)->右サブツリー(または右ノード)の順にアクセスします.
中間パス:左サブツリー(または左ノード)->ルートノード->右サブツリー(または右ノード)の順にアクセスします.
次のパス:左サブツリー(または左ノード)->右サブツリー(または右ノード)->ルートノードの順にアクセスします.
問題解決の考え方:
前の順序で巡回して得られたシーケンスの順序で巡回したデータは、後のデータと同じサブツリー上のデータではないか、同じサブツリーであれば、そのデータは必ずサブツリーのルートノードである.したがって、前の順序で巡回したシーケンスを順次巡回し、巡回したデータに基づいて中順序で巡回したデータを区分することができ、このデータの左側のデータは、そのデータをルートノードとする二叉木の左サブツリーのデータであり、その右側のデータは右サブツリーのデータである.これにより、データを再帰的に復元できます.今日の実装コードは次のとおりです.
コード実装:
ツリーの前順および中順の結果を入力し、ツリーを再構築します.入力された前シーケンスおよび中シーケンスの結果に重複する数値が含まれていないと仮定します.例えば、前シーケンス遍歴シーケンス{1,2,4,7,3,5,6,8}と中シーケンス遍歴シーケンス{4,7,2,1,5,3,8,6}を入力すると、ツリーが再構築され、戻ります.
ツリーの遍歴方法:
前順のループ:ルートノード->左サブツリー(または左ノード)->右サブツリー(または右ノード)の順にアクセスします.
中間パス:左サブツリー(または左ノード)->ルートノード->右サブツリー(または右ノード)の順にアクセスします.
次のパス:左サブツリー(または左ノード)->右サブツリー(または右ノード)->ルートノードの順にアクセスします.
問題解決の考え方:
前の順序で巡回して得られたシーケンスの順序で巡回したデータは、後のデータと同じサブツリー上のデータではないか、同じサブツリーであれば、そのデータは必ずサブツリーのルートノードである.したがって、前の順序で巡回したシーケンスを順次巡回し、巡回したデータに基づいて中順序で巡回したデータを区分することができ、このデータの左側のデータは、そのデータをルートノードとする二叉木の左サブツリーのデータであり、その右側のデータは右サブツリーのデータである.これにより、データを再帰的に復元できます.今日の実装コードは次のとおりです.
コード実装:
public class Solution {
static int index = 0;
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if (pre == null || pre.length == 0) {
return null;
}
return reConstructBinaryTree(pre, in, 0, in.length - 1);
}
public TreeNode reConstructBinaryTree(int [] pre,int [] in, int s, int e) {
if (s > e) {
return null;
}
if (index >= pre.length) {
return null;
}
for(int i = s; i <= e; ++i){
if (in[i] == pre[index]) {
TreeNode result = new TreeNode(pre[index]);
++index;
result.left = reConstructBinaryTree(pre, in, s, i-1);
result.right = reConstructBinaryTree(pre, in, i + 1, e);
return result;
}
}
return null;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] pre = new int[]{1,2,4,3,5,6};
int[] in = new int[]{4,2,1,5,3,6};
Solution solution = new Solution();
TreeNode result = solution.reConstructBinaryTree(pre, in);
System.out.println(result);
}
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}