leetcode:105.前シーケンスと中シーケンスを巡るシーケンス構造ツリー(java)
1163 ワード
package LeetCode;
import java.util.ArrayList;
import java.util.List;
/*
105.
。
:
。
,
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
:
3
/ \
9 20
/ \
15 7
*/
public class BuildTree {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return dfs(0, preorder.length - 1, 0, inorder.length - 1, preorder, inorder);
}
public TreeNode dfs(int ps, int pe, int is, int ie, int[] preorder, int[] inorder) {
if (ps > pe) return null;
TreeNode r = new TreeNode(preorder[ps]);
int mid = -1;
for (int i = 0; i <= ie; i++) {
if (inorder[i] == preorder[ps]) {
mid = i;
break;
}
}
if (mid == -1) return null;
//
// [ps][ps+1...ps+c][ps+c+1...pe]
// [is...mid-1][mid][mid+1...ie]
int c = mid - is;
r.left = dfs(ps + 1, ps + c, is, mid - 1, preorder, inorder);
r.right = dfs(ps + c + 1, pe, mid + 1, ie, preorder, inorder);
return r;
}
}