[Leetcode][python]从前序与中序遍历序列构造二叉树/从中序与后序遍历序列构造二叉树

朱雀 2022-06-12 12:37 135阅读 0赞

## 题目大意 ##

根据二叉树的前序遍历和中序遍历（ 中序和后序）结果生成二叉树  
假设没有重复数字

## 解题思路 ##

参考[给中序和后序遍历][Link 1]  
看到树首先想到要用递归来解题。以这道题为例：如果一颗二叉树为\{1,2,3,4,5,6,7\}，则中序遍历为\{4,2,5,1,6,3,7\}，后序遍历为\{4,5,2,6,7,3,1\}，我们可以反推回去。由于后序遍历的最后一个节点就是树的根。也就是root=1，然后我们在中序遍历中搜索1，可以看到中序遍历的第四个数是1，也就是root。根据中序遍历的定义，1左边的数\{4,2,5\}就是左子树的中序遍历，1右边的数\{6,3,7\}就是右子树的中序遍历。而对于后序遍历来讲，一定是先后序遍历完左子树，再后序遍历完右子树，最后遍历根。于是可以推出：\{4,5,2\}就是左子树的后序遍历，\{6,3,7\}就是右子树的后序遍历。而我们已经知道\{4,2,5\}就是左子树的中序遍历，\{6,3,7\}就是右子树的中序遍历。再进行递归就可以解决问题了。

前序和中序：

root.left = self.buildTree(preorder[1 : index + 1], inorder[0 : index])
    root.right = self.buildTree(preorder[index + 1 : len(preorder)], inorder[index + 1 : len(inorder)])

中序和后序：

root.left = self.buildTree(inorder[0 : index], postorder[0 : index])
    root.right = self.buildTree(inorder[index + 1 : len(preorder)], postorder[index : len(inorder)-1])

## 代码 ##

### 前序和中序 ###

class Solution(object):
        def buildTree(self, preorder, inorder):
            if len(preorder) == 0:
                return None
            if len(preorder) == 1:
                return TreeNode(preorder[0])
            root = TreeNode(preorder[0])
            index = inorder.index(root.val) # 中序中根节点的位置，左边即为左子树，右边由子树
            root.left = self.buildTree(preorder[1 : index + 1], inorder[0 : index])
            root.right = self.buildTree(preorder[index + 1 : len(preorder)], inorder[index + 1 : len(inorder)])
            return root

### 中序和后序 ###

class Solution(object):
        def buildTree(self, inorder, postorder):
            if len(inorder) == 0:
                return None
            if len(inorder) == 1:
                return TreeNode(inorder[0])
            root = TreeNode(postorder[len(postorder) - 1])
            index = inorder.index(postorder[len(postorder) - 1])
            root.left = self.buildTree(inorder[ 0 : index ], postorder[ 0 : index ])
            root.right = self.buildTree(inorder[ index + 1 : len(inorder) ], postorder[ index : len(postorder) - 1 ])
            return root

## 总结 ##

### 二叉树遍历 ###

1.  二叉树的前序、中序、后序遍历（深度优先遍历）  
    遍历即将树的所有结点都访问且仅访问一次。按照根结点访问次序的不同，可以分为前序遍历，中序遍历，后序遍历。  
    前序遍历：根结点 -> 左子树 -> 右子树  
    中序遍历：左子树 -> 根结点 -> 右子树  
    后序遍历：左子树 -> 右子树 -> 根结点  
    ![这里写图片描述][14591414567288.jpg]  
    前序遍历：abdefgc  
    中序遍历：debgfac  
    后序遍历：edgfbca
2.  层次遍历（广度优先遍历）  
    层次遍历：abcdfeg

[Link 1]: http://www.cnblogs.com/zuoyuan/p/3720138.html
[14591414567288.jpg]: https://www.yunaitong.cn/media/14591408147877/14591414567288.jpg