ツリーの再構築(面接アルゴリズム)


タイトルの説明:
ツリーの前順および中順の結果を入力し、ツリーを再構築します.入力された前シーケンスおよび中シーケンスの結果に重複する数値が含まれていないと仮定します.例えば、前シーケンス遍歴シーケンス{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; }
}