题目描述

根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

题目地址: https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

题解

首先回忆下，用前序遍历和中序遍历的方式遍历一颗二叉树：

	      1
	    /   \
	   2     3
	  / \   / \
	 4   5 6   7

前序遍历的结果是:[1,2,4,5,3,6,7]
中序遍历的结果是:[4,2,5,1,6,3,7]
前序遍历的特点是，根节点始终出现在数组的第一位，而中序遍历中根节点出现在数组的中间位置。
根据上面给出的两个数组，首先我们就可以拼出根节点，它就是1。
题目上已说明数组中不存在重复元素，那么由1就可以定位到中序数组的中间位置，中序数组中1左边的部分就是左子树，1右边部分就是右子树。

前序数组怎么切分呢？注意看下面这张图，根节点是橘色，绿色部分是左子树，蓝色部分是右子树。

前序数组的左子树部分+根节点是1,2,4,5，中序数组的左子树部分+根节点是4,2,5,1。这两者的数组长度是一样的。
我们可以根据中序数组的中间位置1，来确定前序数组的左右部分，由于前序数组第一个是根节点，
所以其左边部分是：[1:mid_index]，右半部分是[mid_index+1:]
这里的mid_index是中序数组的中间下标位置。
递归函数实现如下：

1. 终止条件:前序和中序数组为空
2. 根据前序数组第一个元素，拼出根节点，再将前序数组和中序数组分成两半，递归的处理前序数组左边和中序数组左边，递归的处理前序数组右边和中序数组右边。

动画演示如下：

时间复杂度：O(n)
空间复杂度：O(n)

java代码:

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) {
			//用preorder[0]去中序数组中查找对应的元素
			if(preorder[0]==inorder[i]) {
				//将前序数组分成左右两半，再将中序数组分成左右两半
				//之后递归的处理前序数组的左边部分和中序数组的左边部分
				//递归处理前序数组右边部分和中序数组右边部分
				int[] pre_left = Arrays.copyOfRange(preorder,1,i+1);
				int[] pre_right = Arrays.copyOfRange(preorder,i+1,preorder.length);
				int[] in_left = Arrays.copyOfRange(inorder,0,i);
				int[] in_right = Arrays.copyOfRange(inorder,i+1,inorder.length);
				root.left = buildTree(pre_left,in_left);
				root.right = buildTree(pre_right,in_right);
				break;
			}
		}
		return root;
	}
}
                                                                                                         

python代码:

class Solution(object):
	def buildTree(self, preorder, inorder):
		if not (preorder and inorder):
			return None
		# 根据前序数组的第一个元素，就可以确定根节点	
		root = TreeNode(preorder[0])
		# 用preorder[0]去中序数组中查找对应的元素
		mid_idx = inorder.index(preorder[0])
		# 递归的处理前序数组的左边部分和中序数组的左边部分
		# 递归处理前序数组右边部分和中序数组右边部分
		root.left = self.buildTree(preorder[1:mid_idx+1],inorder[:mid_idx])
		root.right = self.buildTree(preorder[mid_idx+1:],inorder[mid_idx+1:])
		return root
                                                                                          

(全文完)

6 次阅读