题目原型:
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
基本思路:
根据前序确定根,然后将中序根据根节点切分成两半,如此递归即可。
public TreeNode buildTree(int[] preorder, int[] inorder) { if(preorder.length==0&&inorder.length==0) { return null; } else { TreeNode root = new TreeNode(preorder[0]); int targetIndex = -1; //在中序序列中找到先序序列的第一个节点值,就是根节点值 for(int i = 0;i<inorder.length;i++) { if(inorder[i]==preorder[0]) { targetIndex = i; break; } } int lenOfLeft = targetIndex; int lenOfRight = inorder.length-targetIndex-1; //找到左子树 int[] leftPreorder = new int[lenOfLeft]; int[] leftInorder = new int[lenOfLeft]; int index = 0; while(index<lenOfLeft) { //赋值左子树 leftPreorder[index] = preorder[index+1]; leftInorder[index] = inorder[index]; index ++; } root.left = buildTree(leftPreorder, leftInorder); //找到右子树 int[] rightPreorder = new int[lenOfRight]; int[] rightInorder = new int[lenOfRight]; index = targetIndex+1; int i = 0; while(i+index<inorder.length) { //赋值右子树 rightPreorder[i] = preorder[i+index]; rightInorder[i] = inorder[i+index]; i++; } root.right = buildTree(rightPreorder, rightInorder); return root; } }