前序遍历和中序遍历树构造二叉树
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
return childNode(preorder, 0, preorder.length, inorder, 0, inorder.length);
}
public TreeNode childNode(int[] preorder, int preStart, int preLen, int[] inorder, int inoStart, int inoLen){
if(inoLen < 1){
return null;
}
TreeNode node = new TreeNode(preorder[preStart]);
int offet = 0;
for(; offet < inoLen; offet++){
if(node.val == inorder[inoStart + offet]){
break;
}
}
node.left = childNode(preorder, preStart + 1, offet, inorder, inoStart, offet);
node.right = childNode(preorder, preStart + offet + 1, preLen - offet - 1, inorder,inoStart + offet + 1, inoLen - offet - 1);
return node;
}
}
解题思路：通过前序遍历可以找到根节点，然后遍历中序遍历数组找到根节点的位置，分别计算左右子树的节点， 通过递归不断计算子节点
