LeetCode 105は、前系列、中系列の遍歴結果に基づいて二叉木を構築する.構想とJava解答

1973 ワード

LeetCode105
主な考え方:
1.先行シーケンスの最初の数、すなわちルート.
2.前のシーケンスを巡るシーケンス全体は、ルート、左サブツリー、右サブツリーの3つの連続部分に分けることができます.
3.中順遍歴のシーケンス全体は、左サブツリー、ルート、右サブツリーの3つの連続部分に分けることができます.
上の3つのアイデアがあって、プログラムをシミュレーションし始めました.
1.preorderシーケンスに従ってrootを見つける
2.rootにより、inorderで左右のサブツリーを特定
3.inorderにおける左右のサブツリーの長さに応じてpreorderで左右のサブツリーを決定する
4.再帰サブツリーの前シーケンス、中シーケンスをrootのために左右のサブツリーを構築する
再帰的な実装は次のとおりです.
/**
 *     、    ,     
 *     :
 *   、      ,         :
 *   : ,   ,   
 *   :   , ,   
 * 
 * @author line
 * @date 2019 2 17    8:46:50
 */
public class Solution105 {

	/**
	 * 1.   preorder  root
	 * 2.   root inorder      
	 * 3.         ,  1.
	 */
	public TreeNode buildTree(int[] preorder, int[] inorder) {
		if (preorder == null || preorder.length == 0)
			return null;
		return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
	}

	/**
	 *         
	 */
	private TreeNode build(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd) {
		TreeNode root = new TreeNode(pre[preStart]); //       ,         !

		int pos = findRoot(root.val, in, inStart, inEnd);
		int leftLen = pos - inStart; //      
		int rightLen = inEnd - pos; //      

		if (leftLen > 0)
			root.left = build(pre, preStart + 1, preStart + leftLen, in, inStart, inStart + leftLen - 1);
		if (rightLen > 0)
			root.right = build(pre, preEnd - rightLen + 1, preEnd, in, inEnd - rightLen + 1, inEnd);

		return root;
	}

	/**
	 *      root.val,  root inorder      ,        
	 */
	private int findRoot(int rootVal, int[] in, int inStart, int inEnd) {
		for (int i = inStart; i <= inEnd; i++) {
			if (in[i] == rootVal)
				return i;
		}
		return -1; // ERROR!                
	}
}

後序、中序も同じで、やめました.ほほほ.
何か間違いがあったら大神さんに指摘してください!!
拡張:
1.前の順序、後の順序で唯一のツリーを構築できますか?
できません.根の位置によって左右の子木、例えば斜めの木を特定することはできないからである.
2.前の順に結果が同じ木を巡ると、必ず同じになりますか?
必ずしもそうとは限らない.前の順序だけで1つのツリーを一意に構築できるかどうかの問題に帰結することができる.中、後序同理.