我的编程空间,编程开发者的网络收藏夹
学习永远不晚

C++如何实现由先序和后序建立二叉树

短信预约 -IT技能 免费直播动态提醒
省份

北京

  • 北京
  • 上海
  • 天津
  • 重庆
  • 河北
  • 山东
  • 辽宁
  • 黑龙江
  • 吉林
  • 甘肃
  • 青海
  • 河南
  • 江苏
  • 湖北
  • 湖南
  • 江西
  • 浙江
  • 广东
  • 云南
  • 福建
  • 海南
  • 山西
  • 四川
  • 陕西
  • 贵州
  • 安徽
  • 广西
  • 内蒙
  • 西藏
  • 新疆
  • 宁夏
  • 兵团
手机号立即预约

请填写图片验证码后获取短信验证码

看不清楚,换张图片

免费获取短信验证码

C++如何实现由先序和后序建立二叉树

今天小编给大家分享一下C++如何实现由先序和后序建立二叉树的相关知识点,内容详细,逻辑清晰,相信大部分人都还太了解这方面的知识,所以分享这篇文章给大家参考一下,希望大家阅读完这篇文章后有所收获,下面我们一起来了解一下吧。

由先序和后序遍历建立二叉树

Return any binary tree that matches the given preorder and postorder traversals.

Values in the traversals pre and post are distinct positive integers.

Example 1:

Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]

Output: [1,2,3,4,5,6,7] 

Note:

  • 1 <= pre.length == post.length <= 30

  • pre[] and post[] are both permutations of 1, 2, ..., pre.length.

  • It is guaranteed an answer exists. If there exists multiple answers, you can return any of them.

这道题给了一棵树的先序遍历和后序遍历的数组,让我们根据这两个数组来重建出原来的二叉树。之前也做过二叉树的先序遍历 [Binary Tree Preorder Traversal](http://www.cnblogs.com/grandyang/p/4146981.html) 和 后序遍历 [Binary Tree Postorder Traversal](http://www.cnblogs.com/grandyang/p/4251757.html),所以应该对其遍历的顺序并不陌生。其实二叉树最常用的三种遍历方式,先序,中序,和后序遍历,只要知道其中的任意两种遍历得到的数组,就可以重建出原始的二叉树,而且正好都在 LeetCode 中有出现,其他两道分别是 [Construct Binary Tree from Inorder and Postorder Traversal](https://www.cnblogs.com/grandyang/p/4296193.html) 和 [Construct Binary Tree from Preorder and Inorder Traversal](https://www.cnblogs.com/grandyang/p/4296500.html)。如果做过之前两道题,那么这道题就没有什么难度了,若没有的话,可能还是有些 tricky 的,虽然这仅仅只是一道 Medium 的题。

我们知道,先序遍历的顺序是 根->左->右,而后序遍历的顺序是 左->右->根,既然要建立树,那么肯定要从根结点开始创建,然后再创建左右子结点,若你做过很多树相关的题目的话,就会知道大多数都是用递归才做,那么创建的时候也是对左右子结点调用递归来创建。心中有这么个概念就好,可以继续来找这个重复的 pattern。由于先序和后序各自的特点,根结点的位置是固定的,既是先序遍历数组的第一个,又是后序遍历数组的最后一个,而如果给我们的是中序遍历的数组,那么根结点的位置就只能从另一个先序或者后序的数组中来找了,但中序也有中序的好处,其根结点正好分割了左右子树,就不在这里细讲了,还是回到本题吧。知道了根结点的位置后,我们需要分隔左右子树的区间,先序和后序的各个区间表示如下:

preorder -> [root] [left subtree] [right subtree]
postorder -> [left subtree] [right substree] [root]

具体到题目中的例子就是:

preorder -> [1] [2,4,5] [3,6,7]
postorder -> [4,5,2] [6,7,3] [root]

先序和后序中各自的左子树区间的长度肯定是相等的,但是其数字顺序可能是不同的,但是我们仔细观察的话,可以发现先序左子树区间的第一个数字2,在后序左右子树区间的最后一个位置,而且这个规律对右子树区间同样适用,这是为啥呢,这就要回到各自遍历的顺序了,先序遍历的顺序是 根->左->右,而后序遍历的顺序是 左->右->根,其实这个2就是左子树的根结点,当然会一个在开头,一个在末尾了。发现了这个规律,就可以根据其来定位左右子树区间的位置范围了。既然要拆分数组,那么就有两种方式,一种是真的拆分成小的子数组,另一种是用双指针来指向子区间的开头和末尾。前一种方法无疑会有大量的数组拷贝,不是很高效,所以我们这里采用第二种方法来做。用 preL 和 preR 分别表示左子树区间的开头和结尾位置,postL 和 postR 表示右子树区间的开头和结尾位置,那么若 preL 大于 preR 或者 postL 大于 postR 的时候,说明已经不存在子树区间,直接返回空指针。然后要先新建当前树的根结点,就通过 pre[preL] 取到即可,接下来要找左子树的根结点在 post 中的位置,最简单的方法就是遍历 post 中的区间 [postL, postR],找到其位置 idx,然后根据这个 idx,就可以算出左子树区间长度为 len = (idx-postL)+1,那么 pre 数组中左子树区间为 [preL+1, preL+len],右子树区间为 [preL+1+len, preR],同理,post 数组中左子树区间为 [postL, idx],右子树区间为 [idx+1, postR-1]。知道了这些信息,就可以分别调用递归函数了,参见代码如下:

解法一:

class Solution {public:    TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {        return helper(pre, 0, (int)pre.size() - 1, post, 0, (int)post.size() - 1);    }    TreeNode* helper(vector<int>& pre, int preL, int preR, vector<int>& post, int postL, int postR) {        if (preL > preR || postL > postR) return nullptr;        TreeNode *node = new TreeNode(pre[preL]);        if (preL == preR) return node;        int idx = -1;        for (idx = postL; idx <= postR; ++idx) {            if (pre[preL + 1] == post[idx]) break;        }        node->left = helper(pre, preL + 1, preL + 1 + (idx - postL), post, postL, idx);        node->right = helper(pre, preL + 1 + (idx - postL) + 1, preR, post, idx + 1, postR - 1);        return node;    }};

我们也可以使用 STL 内置的 find() 函数来查找左子树的根结点在 post 中的位置,其余的地方都跟上面的解法相同,参见代码如下:

解法二:

class Solution {public:    TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {        return helper(pre, 0, (int)pre.size() - 1, post, 0, (int)post.size() - 1);    }    TreeNode* helper(vector<int>& pre, int preL, int preR, vector<int>& post, int postL, int postR) {        if (preL > preR || postL > postR) return nullptr;        TreeNode *node = new TreeNode(pre[preL]);        if (preL == preR) return node;        int idx = find(post.begin() + postL, post.begin() + postR + 1, pre[preL + 1]) - post.begin();        node->left = helper(pre, preL + 1, preL + 1 + (idx - postL), post, postL, idx);        node->right = helper(pre, preL + 1 + (idx - postL) + 1, preR, post, idx + 1, postR - 1);        return node;    }};

为了进一步优化时间复杂度,我们可以事先用一个 HashMap,来建立 post 数组中每个元素和其坐标之间的映射,这样在递归函数中,就不用进行查找了,直接在 HashMap 中将其位置取出来用即可,用空间换时间,也不失为一个好的方法,参见代码如下:

解法三:

class Solution {public:    TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {        unordered_map<int, int> m;        for (int i = 0; i < post.size(); ++i) m[post[i]] = i;        return helper(pre, 0, (int)pre.size() - 1, post, 0, (int)post.size() - 1, m);    }    TreeNode* helper(vector<int>& pre, int preL, int preR, vector<int>& post, int postL, int postR, unordered_map<int, int>& m) {        if (preL > preR || postL > postR) return nullptr;        TreeNode *node = new TreeNode(pre[preL]);        if (preL == preR) return node;        int idx = m[pre[preL + 1]], len = (idx - postL) + 1;        node->left = helper(pre, preL + 1, preL + len, post, postL, idx, m);        node->right = helper(pre, preL + 1 + len, preR, post, idx + 1, postR - 1, m);        return node;    }};

论坛上 [lee215 大神](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/discuss/161268/C%2B%2BJavaPython-One-Pass-Real-O(N)) 提出了一种迭代的写法,借助了栈来做,其实就用个数组就行,模拟栈的后进先出的特性。这种设计思路很巧妙,现根据 pre 数组进行先序创建二叉树,当前我们的策略是,只要栈顶结点没有左子结点,就把当前结点加到栈顶元素的左子结点上,否则加到右子结点上,并把加入的结点压入栈。同时我们用两个指针i和j分别指向当前在 pre 和 post 数组中的位置,若某个时刻,栈顶元素和 post[j] 相同了,说明当前子树已经建立完成了,要将栈中当前的子树全部出栈,直到 while 循环的条件不满足。这样最终建立下来,栈中就只剩下一个根结点了,返回即可,参见代码如下:

解法四:

class Solution {public:    TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {        vector<TreeNode*> st;        st.push_back(new TreeNode(pre[0]));        for (int i = 1, j = 0; i < pre.size(); ++i) {            TreeNode *node = new TreeNode(pre[i]);            while (st.back()->val == post[j]) {                st.pop_back();                ++j;            }            if (!st.back()->left) st.back()->left = node;            else st.back()->right = node;            st.push_back(node);        }        return st[0];    }};

以上就是“C++如何实现由先序和后序建立二叉树”这篇文章的所有内容,感谢各位的阅读!相信大家阅读完这篇文章都有很大的收获,小编每天都会为大家更新不同的知识,如果还想学习更多的知识,请关注编程网行业资讯频道。

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

C++如何实现由先序和后序建立二叉树

下载Word文档到电脑,方便收藏和打印~

下载Word文档

猜你喜欢

C++如何实现由先序和后序建立二叉树

今天小编给大家分享一下C++如何实现由先序和后序建立二叉树的相关知识点,内容详细,逻辑清晰,相信大部分人都还太了解这方面的知识,所以分享这篇文章给大家参考一下,希望大家阅读完这篇文章后有所收获,下面我们一起来了解一下吧。由先序和后序遍历建立
2023-06-19

C++怎么实现由先序和中序遍历二叉树

这篇文章主要介绍了C++怎么实现由先序和中序遍历二叉树的相关知识,内容详细易懂,操作简单快捷,具有一定借鉴价值,相信大家阅读完这篇C++怎么实现由先序和中序遍历二叉树文章都会有所收获,下面我们一起来看看吧。由先序和中序遍历建立二叉树Give
2023-06-19

C++怎么实现二叉树的后序遍历

这篇文章主要介绍“C++怎么实现二叉树的后序遍历”,在日常操作中,相信很多人在C++怎么实现二叉树的后序遍历问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”C++怎么实现二叉树的后序遍历”的疑惑有所帮助!接下来
2023-06-20

C语言中如何实现二叉树的后序遍历

小编给大家分享一下C语言中如何实现二叉树的后序遍历,希望大家阅读完这篇文章之后都有所收获,下面让我们一起去探讨吧!首先我们从两个方面讲解二叉树的后序遍历(递归+迭代)一.二叉树的后序遍历.(递归)思想:首先我们从二叉树的根节点开始先遍历其左
2023-06-29

C++二叉树的前序中序后序非递归怎么实现

这篇“C++二叉树的前序中序后序非递归怎么实现”文章的知识点大部分人都不太理解,所以小编给大家总结了以下内容,内容详细,步骤清晰,具有一定的借鉴价值,希望大家阅读完这篇文章能有所收获,下面我们一起来看看这篇“C++二叉树的前序中序后序非递归
2023-07-05

Java如何实现二叉排序树

这篇文章给大家分享的是有关Java如何实现二叉排序树的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。1 二叉排序树的概述对于常见查找算法,比如顺序查找、二分查找、插入查找、斐波那契查找还不清楚的,可以看这篇文章:常
2023-06-28

C++非递归如何实现二叉树的前中后序遍历

小编给大家分享一下C++非递归如何实现二叉树的前中后序遍历,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!二叉树的前序遍历在不使用递归的方式遍历二叉树时,我们可以使
2023-06-21

如何使用python实现二叉排序树

小编给大家分享一下如何使用python实现二叉排序树,希望大家阅读完这篇文章之后都有所收获,下面让我们一起去探讨吧!方法一(粗暴)#二叉排序树class BTree(): def __init__(self,data):
2023-06-26

JavaScript如何实现二叉树层序遍历

今天小编给大家分享一下JavaScript如何实现二叉树层序遍历的相关知识点,内容详细,逻辑清晰,相信大部分人都还太了解这方面的知识,所以分享这篇文章给大家参考一下,希望大家阅读完这篇文章后有所收获,下面我们一起来了解一下吧。题目描述给你一
2023-07-05

C++二叉树的前序中序后序非递归实现方法详细讲解

前序遍历的顺序是根、左、右。任何一颗树都可以认为分为左路节点,左路节点的右子树。先访问左路节点,再来访问左路节点的右子树。把访问左路节点的右子树看成一个子问题,就可以完整递归访问了
2023-03-08

C语言线索二叉树的前中后如何创建和遍历

这篇“C语言线索二叉树的前中后如何创建和遍历”文章的知识点大部分人都不太理解,所以小编给大家总结了以下内容,内容详细,步骤清晰,具有一定的借鉴价值,希望大家阅读完这篇文章能有所收获,下面我们一起来看看这篇“C语言线索二叉树的前中后如何创建和
2023-06-29

编程热搜

  • Python 学习之路 - Python
    一、安装Python34Windows在Python官网(https://www.python.org/downloads/)下载安装包并安装。Python的默认安装路径是:C:\Python34配置环境变量:【右键计算机】--》【属性】-
    Python 学习之路 - Python
  • chatgpt的中文全称是什么
    chatgpt的中文全称是生成型预训练变换模型。ChatGPT是什么ChatGPT是美国人工智能研究实验室OpenAI开发的一种全新聊天机器人模型,它能够通过学习和理解人类的语言来进行对话,还能根据聊天的上下文进行互动,并协助人类完成一系列
    chatgpt的中文全称是什么
  • C/C++中extern函数使用详解
  • C/C++可变参数的使用
    可变参数的使用方法远远不止以下几种,不过在C,C++中使用可变参数时要小心,在使用printf()等函数时传入的参数个数一定不能比前面的格式化字符串中的’%’符号个数少,否则会产生访问越界,运气不好的话还会导致程序崩溃
    C/C++可变参数的使用
  • css样式文件该放在哪里
  • php中数组下标必须是连续的吗
  • Python 3 教程
    Python 3 教程 Python 的 3.0 版本,常被称为 Python 3000,或简称 Py3k。相对于 Python 的早期版本,这是一个较大的升级。为了不带入过多的累赘,Python 3.0 在设计的时候没有考虑向下兼容。 Python
    Python 3 教程
  • Python pip包管理
    一、前言    在Python中, 安装第三方模块是通过 setuptools 这个工具完成的。 Python有两个封装了 setuptools的包管理工具: easy_install  和  pip , 目前官方推荐使用 pip。    
    Python pip包管理
  • ubuntu如何重新编译内核
  • 改善Java代码之慎用java动态编译

目录