LeetCode算法第105题：从前序与中序遍历序列构造二叉树-搜搜看看

题目描述：

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:

你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
 3
 / \
 9 20
 / \
 15 7

思路：

二叉树的前序遍历顺序为根节点 -> 左子树 -> 右子树；

中序遍历顺序为左子树 -> 根节点 -> 右子树。

因此当我们拿到一个二叉树的前序与中序遍历顺序后，可以确认根节点为前序遍历数组的首元素，然后在中序遍历数组中找到这个根节点，根节点之前的元素为这个二叉树的左子树，根节点之后的元素为这个二叉树的右子树。

使用相同的思路构造二叉树的左子树与右子树，即可得到最终结果。

Java代码：

 public TreeNode buildTree(int[] preorder, int[] inorder) {
 if(null == preorder || preorder.length == 0){
 return null;
 }
 return buildTree(preorder,inorder,0,0,inorder.length);
 }

 public TreeNode buildTree(int[] preorder, int[] inorder,int preStart,int inStart,int inEnd) {
 TreeNode root = new TreeNode(preorder[preStart]);
 for(int i = inStart;i  if(inorder[i] == preorder[preStart]){
 root.left = inStart == i ? null : buildTree(preorder,inorder,preStart+1,inStart,i);
 root.right = i+1 == inEnd ? null : buildTree(preorder,inorder,preStart+(i - inStart + 1),i+1,inEnd);
 break;
 }
 }
 return root;
 }

本文来自投稿，不代表本人立场，如若转载，请注明出处：http://www.sosokankan.com/article/1518660.html

LeetCode算法第105题：从前序与中序遍历序列构造二叉树

相关推荐