描述
Given preorder and inorder traversal of a tree, construct the binary tree.
Note: You may assume that duplicates do not exist in the tree.先序和中序、后序和中序可以唯一确定一棵二叉树
时间复杂度O(n)，空间复杂度O(logn)
// TreeNode.java
public class TreeNode {
public TreeNode left;
public TreeNode right;
public int val;
public TreeNode(int val) {
this.val = val;
this.left = null;
this.right = null;
}
}
// Solution.java
public class Solution {
public TreeNode buildTree(int[] preOrder, int[] inOrder) {
if(preOrder == null || inOrder==null || preOrder.length != inOrder.length)
return null;
return buildTree(preOrder, 0, preOrder.length-1,
inOrder, 0, inOrder.length-1);
}
public TreeNode buildTree(int[] preOrder, int preStart, int preEnd,
int[] inOrder, int inStart, int inEnd ) {
if(preStart > preEnd || inStart > inEnd)
return null;
int rootIdx = -1;
int rootVal = preOrder[preStart];
for(int i = inStart; i <= inEnd; ++i) {
if(inOrder[i] == rootVal) {
rootIdx = i;
break;
}
}
if(rootIdx < 0)
return null;
int len = rootIdx - inStart;
TreeNode root = new TreeNode(rootVal);
root.left = buildTree(preOrder, preStart+1, preStart+len,
inOrder, inStart, rootIdx-1);
root.right = buildTree(preOrder, preStart+len+1, preEnd,
inOrder, rootIdx+1, inEnd);
return root;
}
}
