(分治算法4) leecode 105 从前序与中序遍历构建二叉树

题目描述

给定两个整数数组preorder和inorder，其中preorder是二叉树的先序遍历，inorder是同一棵树的中序遍历，请构造二叉树并且返回其根节点。

分治算法求解

前序遍历的第一个就是根节点，根据根节点的位置，我们可以在中序遍历中知道这棵树的左子树和右子树。
然后从子树中，前序遍历的第一个元素就是左子树的根节点，这样的话我们就可以利用分治算法来构建二叉树。

class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {if(preorder.length == 0 || inorder.length == 0){return null;}TreeNode root = new TreeNode(preorder[0]);for(int i =0 ; i < preorder.length; i++){//这句话就是找到子树的根if(preorder[0] == inorder[i]){root.left = buildTree(Arrays.copyOfRange(preorder,1,i+1),Arrays.copyOfRange(inorder,0,i));root.right = buildTree(Arrays.copyOfRange(preorder,i+1,preorder.length), Arrays.copyOfRange(inorder,i+1,inorder.length));break;}}return root;}
}