414,剑指 Offer-重建二叉树

2021年11月25日 阅读数:5
这篇文章主要向大家介绍414,剑指 Offer-重建二叉树,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

414,剑指 Offer-重建二叉树_二叉树

Tough time don't last, tough people do.node

没有过不去的坎, 只有打不倒的人。算法

问题描述编程

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

 

例如,给出ide

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

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

 

返回以下的二叉树:blog

    3开发

   / \it

  9  20

    /  \

   15   7

限制:

  • 0 <= 节点个数 <= 5000

 

问题分析

这题和以前讲过的一道题重复了,399,从前序与中序遍历序列构造二叉树,这两道题实际上是彻底同样的,除了以前讲过的3种方法之外,咱们今天再来说一种解法,这种思想来源于403,验证二叉搜索树的第一种解法。前序遍历的第一个元素确定是根节点,那么前序遍历的第一个节点在中序位置以前的都是根节点的左子节点,以后的都是根节点的右子节点,咱们来简单画个图看一下

414,剑指 Offer-重建二叉树_编程开发_02

这里是随便举个例子,咱们看到前序遍历的3确定是根节点,那么在中序遍历中,3前面的都是3左子节点的值,3后面的都是3右子节点的值,

他真正的结构是这样的

414,剑指 Offer-重建二叉树_编程开发_03

咱们来看下代码

 1private int in = 0;
2private int pre = 0;
3
4public TreeNode buildTree(int[] preorder, int[] inorder) {
5    return build(preorder, inorder, Integer.MIN_VALUE);
6}
7
8private TreeNode build(int[] preorder, int[] inorder, int stop) {
9    if (pre >= preorder.length)
10        return null;
11    if (inorder[in] == stop) {
12        in++;
13        return null;
14    }
15
16    TreeNode node = new TreeNode(preorder[pre++]);
17    node.left = build(preorder, inorder, node.val);
18    node.right = build(preorder, inorder, stop);
19    return node;
20}

 

总结

关于二叉树的算法题其实有不少,这里讲的也只是冰山一角,搞懂了上面和前面的几个关于二叉树的题,对二叉树算法相关题的理解也会进一步加深

 

 

414,剑指 Offer-重建二叉树_二叉树_04

410,剑指 Offer-从尾到头打印链表

408,剑指 Offer-替换空格

406,剑指 Offer-二维数组中的查找

404,剑指 Offer-数组中重复的数字

 

414,剑指 Offer-重建二叉树_编程开发_05

长按上图,识别图中二维码以后便可关注。

 

若是喜欢这篇文章就点个"赞"吧