Given preorder and inorder traversal of a tree, construct the binary tree.
题目大意:给定一个二叉树的前序和中序序列,构建出这个二叉树。
解题思路:跟中序和后序一样,在先序中取出根节点,然后在中序中找到根节点,划分左右子树,递归构建这棵树,退出条件就是左右子树长度为1,则返回这个节点,长度为0则返回null。
Talk is cheap:
public TreeNode buildTree(int[] preorder, int[] inorder) { if (preorder == null || inorder == null || inorder.length == 0 || preorder.length == 0) { return null; } int preLen = preorder.length; int inLen = inorder.length; TreeNode root = new TreeNode(preorder[0]); if (preLen == 1) { return root; } int pos = 0; for (int i = 0; i < inLen; i++) { if (inorder[i] == preorder[0]) { pos = i; break; } } int[] preLeft = Arrays.copyOfRange(preorder, 1, pos + 1); int[] inLeft = Arrays.copyOfRange(inorder, 0, pos); int[] preRight = Arrays.copyOfRange(preorder, pos + 1, preLen); int[] inRight = Arrays.copyOfRange(inorder, pos + 1, inLen); root.left = buildTree(preLeft, inLeft); root.right = buildTree(preRight, inRight); return root; }