面试题7：重建二叉树

题目： https://www.nowcoder.com/ta/coding-interviews

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

思考：

前序遍历的第一个值是二叉树的根节点，中旬遍历中根节点（索引为i）前边的都是左子树的值（对应前序遍历[1:i+1]中的元素），后边的是右子树的值（对应前序遍历[i+1:]中的元素）；

递归重复以上过程：取前序遍历[1:i+1]和中序遍历[:i]中的值重复上一个过程得到左子树,取前序遍历[i+1:]和中序遍历[i+1：]得到右子树

#定义树节点
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        
def PrintFromTopToBottom(root):#打印二叉树（从上往下，同层节点从左至右打印）
    array = []
    result = []
    if root == None:
        return result

    array.append(root)
    while array:
        newNode = array.pop(0)
        result.append(newNode.val)
        if newNode.left != None:
            array.append(newNode.left)
        if newNode.right != None:
            array.append(newNode.right)
    return result

方法1

class Solution:
    def reConstructBinaryTree(self, preorder,inorder):
        if len(preorder) == 0:
            return None
        if len(preorder) == 1:
            return TreeNode(preorder[0])
        else:
            index = inorder.index(preorder[0])#得到根节点在中序遍历中的索引
            node = TreeNode(preorder[0])#根节点
            
            preorderLeft = preorder[1:index+1]#左子树的元素
            inorderLeft = inorder[:index]
            preorderRight = preorder[index+1:]#右子树的元素
            inorderRight = inorder[index+1:]
            
            node.left = self.reConstructBinaryTree(preorderLeft,inorderLeft)#递归调用重建方法self.XX()
            node.right = self.reConstructBinaryTree(preorderRight,inorderRight)
        return node

solution = Solution()
preorder_seq = [1, 2, 4, 7, 3, 5, 6, 8]
middleorder_seq = [4, 7, 2, 1, 5, 3, 8, 6]
# print(middleorder_seq[-4:])
treeRoot1 = solution.reConstructBinaryTree(preorder_seq, middleorder_seq)
newArray = PrintFromTopToBottom(treeRoot1)
print(newArray)

[5, 3, 8, 6]
[1, 2, 3, 4, 5, 6, 7, 8]

方法2

class Solution:
    def construct_tree(self, preorder=None, inorder=None):
        """
        构建二叉树
        """
        if not preorder or not inorder:
            return None
        index = inorder.index(preorder[0])
        left = inorder[0:index]
        right = inorder[index+1:]
        root = TreeNode(preorder[0])
        root.left = construct_tree(preorder[1:1+len(left)], left)#这里其实有len(left)=index
        root.right = construct_tree(preorder[-len(right):], right)
        #preorder[-3:]表示从-3到末尾处，包含-3这个索引（倒数第三）位置的元素
        return root

[1, 2, 3, 4, 5, 6, 7, 8]

参考：

https://blog.csdn.net/Datawhale/article/details/81948283

https://blog.csdn.net/fuxuemingzhu/article/details/70303139

https://blog.csdn.net/u010005281/article/details/79493413