欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

【剑指offer 07】用迭代和递归两种方法重构二叉树(python实现).md

程序员文章站 2022-06-21 22:50:56
本文讲解一个经典的面试题,使用 python 通过迭代和递归两种方法重构二叉树。题目描述输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如,给出:前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7]返回如下的二叉树:3 / \ 9 20 / \ 15 7限制:0 <= 节点个数 <= 5000。递归方法二叉树的前序遍...

本文讲解一个经典的面试题,使用 python 通过迭代和递归两种方法重构二叉树。

题目描述

输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如,给出:

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树:

	3
   / \
  9  20
    /  \
   15   7

限制:0 <= 节点个数 <= 5000。

递归方法

二叉树的前序遍历顺序是:根节点、左子树、右子树,每个子树的遍历顺序同样满足前序遍历顺序。

二叉树的中序遍历顺序是:左子树、根节点、右子树,每个子树的遍历顺序同样满足中序遍历顺序。

前序遍历的第一个节点是根节点,只要找到根节点在中序遍历中的位置,在根节点之前被访问的节点都位于左子树,在根节点之后被访问的节点都位于右子树,由此可知左子树和右子树分别有多少个节点。

由于树中的节点数量与遍历方式无关,通过中序遍历得知左子树和右子树的节点数量之后,可以根据节点数量得到前序遍历中的左子树和右子树的分界,因此可以进一步得到左子树和右子树各自的前序遍历和中序遍历,可以通过递归的方式,重建左子树和右子树,然后重建整个二叉树。

递归方法的基准情形有两个:判断前序遍历的下标范围的开始和结束,若开始大于结束,则当前的二叉树中没有节点,返回空值 null。若开始等于结束,则当前的二叉树中恰好有一个节点,根据节点值创建该节点作为根节点并返回。若开始小于结束,则当前的二叉树中有多个节点。在中序遍历中得到根节点的位置,从而得到左子树和右子树各自的下标范围和节点数量,知道节点数量后,在前序遍历中即可得到左子树和右子树各自的下标范围,然后递归重建左子树和右子树,并将左右子树的根节点分别作为当前根节点的左右子节点。

展开来说,以下面的图为例子:

【剑指offer 07】用迭代和递归两种方法重构二叉树(python实现).md

根据前序遍历得知,3 是根节点。

根据中序遍历得知,9 是左子树且节点数为1,[15, 20, 7] 是右子树且节点数为3。

根据上一步得到的左子树右子树节点个数,可以将前序遍历划分为左子树、右子树。

前序遍历中左子树的节点包含 [9] ,于是 9 就是左子树根节点。另外,还可以知道左子树在前序遍历中的左右边界为 [1, 1],由于左右边界相同,说明当前的左子树其实是叶节点,续划分左子树右子树的话,应该返回None。

前序遍历中右子树的节点包含 [20, 15, 7] ,于是 20 是右子树根节点。另外,右子树在前序遍历中的边界为 [2, 4],左右边界不相同,需要以20作为根节点继续划分子树。如下图所示:

【剑指offer 07】用迭代和递归两种方法重构二叉树(python实现).md

中序遍历中发现 20 的左子树有一个节点,右子树有一个节点,因此在前序遍历中可以确定 [15] 为左子树,[7] 为右子树。由于 20 的左右子树在前序遍历中边界相同,所以是叶节点,树构建完毕。

根据上面的理论,可以得到下面的代码实现:

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    # 递归(1) 56 ms
    def buildTree(self, preorder, inorder):
        # 将前序遍历序列保存为属性,方便递归时得到 val
        self.po = preorder
        # 构造一个字典,方便确定边界
        self.dic = {}
        for i in range(len(inorder)):
            self.dic[inorder[i]] = i
        # 开始递归构造树
        return self.recur(0, 0, len(inorder)-1)

    def recur(self, pre_root, in_left, in_right):
        # 由于叶子节点没有左右子树,弱继续划分则应该得到None
        # 因此,当左边界大于右边界时结束递归
        if in_left > in_right:
            return 
        # 根据根节点的位置得到 val
        node = self.po[pre_root]
        # 构造根节点
        root = TreeNode(node)
        # 得到根节点的 val 在中序遍历序列中的位置
        i = self.dic[node]
        # 构造左子树
        # 左子树根节点为前序遍历序列根节点右边第一个元素
        # 右边界为中序遍历根节点位置左边的一个位置
        root.left = self.recur(pre_root+1, in_left, i-1)
        # 构造右子树
        # (i-in_left) 表示左子树节点的个数
        # 右子树根节点为前序遍历序列根节点右边第(i-in_left)+1个元素
        # 左边界为中序遍历根节点位置右边的一个位置
        root.right = self.recur(pre_root+(i-in_left)+1, i+1, in_right)
        return root
        
        
t = Solution().buildTree([3,9,20,15,7], [9,3,15,20,7])
print(t.val, t.left.val, t.right.val)

时间复杂度 O(N): N 为树的节点数量。初始化 HashMap 需遍历 inorder ,占用 O(N) ;递归共建立 N 个节点,每层递归中的节点建立、搜索操作占用 O(1),因此递归占用 O(N)。(最差情况为所有子树只有左节点,树退化为链表,此时递归深度 O(N) ;平均情况下递归深度 O(log2Nlog_2 N)。

空间复杂度 O(N): HashMap 使用 O(N) 额外空间;递归操作中系统需使用 O(N) 额外空间。

基于递归的思想,还有一种写法:

class Solution:
    # 递归(2) 192 ms
    def buildTree(self, preorder, inorder):
        if not preorder:
            return None
        loc = inorder.index(preorder[0])
        root = TreeNode(preorder[0])
        root.left = self.buildTree(preorder[1 : loc + 1], inorder[ : loc])
        root.right = self.buildTree(preorder[loc+1 : ], inorder[loc+1: ])
        return root

这样的写法更多的使用了python内置的方法,看起来十分简洁,就是执行时间长了一些。

迭代方法

例如要重建的是如下二叉树:

        3
       / \
      9  20
     /  /  \
    8  15   7
   / \
  5  10
 /
4

其前序遍历和中序遍历如下:

preorder = [3,9,8,5,4,10,20,15,7]
inorder = [4,5,8,10,9,3,15,20,7]

解题步骤:

  • 使用前序遍历的第一个元素(例如 3)创建根节点。
  • 创建一个栈,将根节点 (例如 3) 压入栈内,接下来准备一路向左构建左子树。
  • 初始化中序遍历下标为 0。
  • 遍历 preorder 中还未访问过的每个元素(例如 [9,8,5,4,10,20,15,7]),判断栈顶元素是否等于中序遍历下标指向的元素 (例如 4) 。
  • 若栈顶元素不等于中序遍历下标指向的元素 (例如 4) ,说明当前的 preorder 元素还没到达树的最左端,则将当前元素 (例如 9) 作为其上一个元素(例如栈顶元素 3)的左子节点,并将当前元素 (例如 9) 压入栈内,继续对 preorder 中还未访问过的每个元素(例如 [8,5,4,10,20,15,7]) 重复此过程,一直向左构建子树 (例如可以得到 3->9->8->5->4),并将构建的子树入栈 (例如得到栈 [3,9,8,5,4])。
  • 若栈顶元素(即上一次遍历的元素,例如 4)等于中序遍历下标指向的元素 (例如 4) ,则从栈内弹出一个元素 (例如 弹出 4),同时令中序遍历下标指向下一个元素 (例如 5) ,之后继续判断栈顶元素 (例如 5) 是否等于中序遍历下标指向的元素,若相等则重复该操作,直至栈为空或者元素不相等(例如 8 出栈以后,栈顶元素 9 与中序遍历元素 10 不同),这说明在栈顶元素(例如 8) 产生了分支,因此令当前元素 (例如 10) 作为最后一个相等元素(即刚刚出栈的元素 8 )的右节点。
  • 遍历结束,返回根节点。

代码如下:

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    # 迭代 	56 ms
    def buildTree(self, preorder, inorder):
        if not preorder:
            return None    
        root = TreeNode(preorder[0])
        stack = []
        L = len(preorder)
        stack.append(root)
        index = 0               
        for i in range(1, L):
            preorderval = preorder[i]
            # 中序的当前 i 不等于栈顶时表示还没搜索到根节点,
            # 每次append的的preorder[i]其实都是其左子树,左子树的左子树,...
            if stack[-1].val != inorder[index]:     #进左子树
                node = stack[-1]
                node.left = TreeNode(preorderval)
                stack.append(node.left)
            #一旦中序inorder里的元素与栈顶相等时,表示左子树已经走完了
            else:
                # 如果栈弹空了,表示根节点root出栈了
                # == 时表示当前出栈元素没有右孩子
                while stack and stack[-1].val == inorder[index]:
                    node = stack[-1]
                    stack.pop()
                    index += 1     
                node.right = TreeNode(preorderval)      
                stack.append(node.right)
        return root     

t = Solution().buildTree([3,9,20,15,7], [9,3,15,20,7])
print(t.val, t.left.val, t.right.val)

时间复杂度:O*(*n) ,前序遍历和后序遍历都被遍历。

空间复杂度:O*(*n) ,额外使用栈存储已经遍历过的节点。

参考文章:

面试题07. 重建二叉树

迭代-栈图解:剑指07. (前序中序)重建二叉树:递归

本文地址:https://blog.csdn.net/VariableX/article/details/107659537