python实现二叉树的重建1 之由前序遍历和中序遍历重建

ゝ一世哀愁。 2022-05-15 06:46 149阅读 0赞

# 前言 #

此题是关于树的面试题目的常见题型，题目的含义很清晰，这个就不用多说了

# 解法 #

关于这道题的解法有很多不同的样式，通用的解法是这样的：  
假如现在我们有如下两个遍历的情况

preorder: [1, 2, 4, 5, 3, 6]
    inorder: [4, 2, 5, 1, 6, 3]

那么我们建树的办法通常是

1.用先序遍历的第一个元素也就是1，作为root
    2.然后在inorder中查找1的位置
    3.然后将inorder以1分割成两半，一半表示左子树，一半表示右子树，这里就是[4, 2, 5]和[6, 3]
    4.然后使用[2, 4, 5]和[4, 2, 5]去构建左子树，[3, 6]和[6, 3]去构建右子树

我们以此可以写出如下的解决办法：

# 树的定义
    class TreeNode:
        def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None

def buildTree(self, preorder, inorder):
        if inorder:
            ind = inorder.index(preorder.pop(0))
            root = TreeNode(inorder[ind])
            root.left = self.buildTree(preorder, inorder[0:ind])
            root.right = self.buildTree(preorder, inorder[ind+1:])
            return root

如果我们考虑到不停的`pop(0)`,这样效率不是很高的话，我们可稍微优化一下：

def buildTree(self, preorder, inorder):
            """ :type preorder: List[int] :type inorder: List[int] :rtype: TreeNode """
            def build(preorder, inorder):
                if inorder:
                    ind = inorder.index(preorder.pop())
                    root = TreeNode(inorder[ind])
                    root.left = build(preorder, inorder[ind+1:])
                    root.right = build(preorder, inorder[:ind])
                    return root
            preorder.reverse()
            inorder.reverse()
            return build(preorder, inorder)

这里我们先将列表翻转了，这样，我们弹栈的时候，就不会造成很多的列表元素的移动。  
**但是即使如此，我们考虑最坏的情况：这个树不是平衡的而是一颗只有左子树的斜树，那么，他的先序遍历和中序遍历是完全相反的，整个算法过程中进行第二步的查找过程时候所花费的时间为`O(n^2)`,由于我们使用的递归的实现方法，所以空间复杂度也是O(n^2)**

# 优化时间复杂度 #

我们可以省略在Inorder中查找这一步，不是找到1在inorder中的index，把数组分成几个部分，然后递归它们上，而是递归到全部剩下的数组，当你遇到1的时候就停止，具体的实现如下：

def buildTree(self, preorder, inorder):
        def build(stop):
            if inorder and inorder[-1] != stop:
                root = TreeNode(preorder.pop())
                root.left = build(root.val)
                inorder.pop()
                root.right = build(stop)
                return root
        preorder.reverse()
        inorder.reverse()
        return build(None)

其中当我们遇到了在inorder中遇到了`stop`时候，证明我们在这里树要开始“转向”了，即从左子树变成右子树了，所以我们继续接着上一次的`stop`来走

# 再优化空间复杂度 #

def buildTree2(self, preorder, inorder):
            if len(preorder) == 0:
                return None
            i, j = 1, 0
            root = TreeNode(preorder[0])
            stack = [root]
            while i < len(preorder):
                node = TreeNode(preorder[i])
                tmp = None
                while stack and stack[-1].val == inorder[j]:
                    tmp = stack.pop()
                    j += 1
                if tmp:
                    tmp.right = node
                else:
                    stack[-1].left = node
                stack.append(node)
                i += 1
            return root

我们现在不使用递归了，而是直接使用栈来解决这个问题，我们从头到尾过一遍preorder，把过的元素存在栈中，如果发现preorder中有元素在inorder中出现了，就开始把栈中元素弹出来，之所以这样做，是因为好比已经建完了半边的树，现在要换半边继续建树了

# 参考 #

[leetcode solution 1][]  
[leetcode solution 2][]

[leetcode solution 1]: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/discuss/34543/Simple-O%28n%29-without-map
[leetcode solution 2]: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/discuss/34579/Python-short-recursive-solution.