题目
描述
根据前序遍历和中序遍历树构造二叉树.
样例
样例 1:
输入: in-order = [], pre-order = []
输出: null
样例 2:
输入: in-order = [1,2,3], pre-order = [2,1,3]
输出:
2
/ \
1 3
注意事项
你可以假设树中不存在相同数值的节点
解答
思路
根据注意事项，前序遍历的节点从根节点开始，那么在中序遍历中对应的节点的左边就是其左子树，右边就是其右子树了。
代码
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param inorder: A list of integers that inorder traversal of a tree
* @param postorder: A list of integers that postorder traversal of a tree
* @return: Root of a tree
*/
public TreeNode buildTree(int[] preorder, int[] inorder) {
// write your code here
if (preorder.length == 0 && inorder.length == 0) {
return null;
}
TreeNode root = new TreeNode(preorder[0]);
int length = inorder.length;
int rootIndex = 0;
for (int a : inorder) {
if (a == preorder[0]) {
break;
}
rootIndex++;
}
root.left = buildTree(java.util.Arrays.copyOfRange(preorder, 1, 1 + rootIndex), java.util.Arrays.copyOfRange(inorder, 0, rootIndex));
root.right = buildTree(java.util.Arrays.copyOfRange(preorder, rootIndex + 1, length), java.util.Arrays.copyOfRange(inorder, rootIndex + 1, length));
return root;
}
}
