高频算法面试题（三十二）- 重建二叉树

发表于

「这是我参与11月更文挑战的第 17 天，活动详情查看：2021最后一次更文挑战」

刷算法题，从来不是为了记题，而是练习把实际的问题抽象成具体的数据结构或算法模型，然后利用对应的数据结构或算法模型来进行解题。个人觉得，带着这种思维刷题，不仅能解决面试问题，也能更多的学会在日常工作中思考，如何将实际的场景抽象成相应的算法模型，从而提高代码的质量和性能

重建二叉树

题目来源：LeetCode-105. 从前序与中序遍历序列构造二叉树

题目描述

给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点

示例

示例 1

1.png

1
2
yaml复制代码Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

示例 2

1
2
ini复制代码Input: preorder = [-1], inorder = [-1]
Output: [-1]

提示：

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • 3000 <= preorder[i], inorder[i] <= 3000
  • preorder 和 inorder 均无重复元素
  • inorder 均出现在 preorder
  • preorder 保证为二叉树的前序遍历序列
  • inorder 保证为二叉树的中序遍历序列

解题

解法一：递归

思路

首先我们需要知道的是，如何根据前序遍历和中序遍历来推出一棵树长什么样

根据前序遍历的结果，我们可以知道什么？

显然我们可以知道，前序遍历的第一个节点就是根节点

根据中序遍历的结果，我们可以知道什么？

我们可以知道，在中序遍历中，根节点的左边部分，都在树的左子树上。根节点的右边部分，都在树的右子树上

比如例一种给出

1
2
复制代码前序遍历：3,9,20,15,7
中序遍历：9,3,15,20,7

首先根据前序遍历，可以知道树的根节点是3

然后根据中序遍历，可以知道9在树的左子树上，15、20、7在树的右子树上，因此，首先第一步我们可以得出下边这样的树结构

2.png

左边只有一个节点，我们可以直接确定位置，右边有多个节点，因此我们需要继续重复上边的步骤。首先15、20、7这三个结点的前序遍历是20、15、7（从原来给的前序遍历结果中可以知道），中序遍历是15、20、7

所以可以知道这三个结点中，20是根节点，15是左子树，20是右子树

3.png
理解了上边，你会发现，非常适合用递归来实现。如果你不知道，我怎么知道一道题适合用递归来实现？可以看这篇总结

树的递归代码挺难想到的，有时候有思路也写不出来代码。个人感觉比较有效的办法就是多做二叉树的题，直接分类做，先把LeetCode的前300道题中的二叉树题刷一下，做的多了就有感觉了（当然，所有的题，并不是做一遍就行，要做到能不看答案就能写出bug free的代码，当然少不了勤总结）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
go复制代码//构建二叉树树
func buildTree(preorder []int, inorder []int) *TreeNode {
	if len(preorder) == 0 {
		return nil
	}

	root := TreeNode{preorder[0], nil, nil}
	//找到跟结点在中序遍历结果中的位置
	i := 0
	for ; i < len(inorder); i++ {
		if preorder[0] == inorder[i] {
			break
		}
	}

	root.Left = buildTree(preorder[1:len(inorder[:i])+1], inorder[:i]) //因为切片是左闭右开的，所以需要+1
	root.Right = buildTree(preorder[len(inorder[:i])+1:], inorder[i+1:])

	return &root
}

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%