LeetCode 105は、前系列、中系列の遍歴結果に基づいて二叉木を構築する.構想とJava解答
1973 ワード
LeetCode105
主な考え方:
1.先行シーケンスの最初の数、すなわちルート.
2.前のシーケンスを巡るシーケンス全体は、ルート、左サブツリー、右サブツリーの3つの連続部分に分けることができます.
3.中順遍歴のシーケンス全体は、左サブツリー、ルート、右サブツリーの3つの連続部分に分けることができます.
上の3つのアイデアがあって、プログラムをシミュレーションし始めました.
1.preorderシーケンスに従ってrootを見つける
2.rootにより、inorderで左右のサブツリーを特定
3.inorderにおける左右のサブツリーの長さに応じてpreorderで左右のサブツリーを決定する
4.再帰サブツリーの前シーケンス、中シーケンスをrootのために左右のサブツリーを構築する
再帰的な実装は次のとおりです.
後序、中序も同じで、やめました.ほほほ.
何か間違いがあったら大神さんに指摘してください!!
拡張:
1.前の順序、後の順序で唯一のツリーを構築できますか?
できません.根の位置によって左右の子木、例えば斜めの木を特定することはできないからである.
2.前の順に結果が同じ木を巡ると、必ず同じになりますか?
必ずしもそうとは限らない.前の順序だけで1つのツリーを一意に構築できるかどうかの問題に帰結することができる.中、後序同理.
主な考え方:
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つのツリーを一意に構築できるかどうかの問題に帰結することができる.中、後序同理.