LEETCODE 105. 从前序与中序遍历序列构造二叉树
题目描述
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如,给出
前序遍历 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
是中序数组的中间下标位置。
递归函数实现如下:
-
终止条件:前序和中序数组为空 -
根据前序数组第一个元素,拼出根节点,再将前序数组和中序数组分成两半,递归的处理前序数组左边和中序数组左边,递归的处理前序数组右边和中序数组右边。
动画演示如下:
时间复杂度: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
(全文完)
8 次阅读