这篇文章主要介绍了C++怎么实现由中序和后序遍历二叉树的相关知识，内容详细易懂，操作简单快捷，具有一定借鉴价值，相信大家阅读完这篇C++怎么实现由中序和后序遍历二叉树文章都会有所收获，下面我们一起来看看吧。Given inorder and postorder traversal of a tree, construct the binary tree.Note:
You may assume that duplicates do not exist in the tree.For example, giveninorder =[9,3,15,20,7]
postorder = [9,15,7,20,3]Return the following binary tree: 3
/
9 20
/
15 7这道题要求从中序和后序遍历的结果来重建原二叉树，我们知道中序的遍历顺序是左-根-右，后序的顺序是左-右-根，对于这种树的重建一般都是采用递归来做，可参见博主之前的一篇博客Convert Sorted Array to Binary Search Tree。针对这道题，由于后序的顺序的最后一个肯定是根，所以原二叉树的根结点可以知道，题目中给了一个很关键的条件就是树中没有相同元素，有了这个条件就可以在中序遍历中也定位出根节点的位置，并以根节点的位置将中序遍历拆分为左右两个部分，分别对其递归调用原函数。代码如下：上述代码中需要小心的地方就是递归是 postorder 的左右 index 很容易写错，比如 pLeft + i – iLeft – 1, 这个又长又不好记，首先我们要记住 i – iLeft 是计算 inorder 中根节点位置和左边起始点的距离，然后再加上 postorder 左边起始点然后再减1。我们可以这样分析，如果根结点就是左边起始点的话，那么拆分的话左边序列应该为空集，此时 i – iLeft 为0， pLeft + 0 – 1
下面来看一个例子, 某一二叉树的中序和后序遍历分别为：Inorder: 11 4 5 13 8 9Postorder: 11 4 13 9 8 5 11 4 5 13 8 9 => 511 4 13 9 8 5 / 11 4 13 8 9 => 511 4 13 9 8 / 4 811 13 9 => 511 13 9 / 4 8 / / 11 13 9关于“C++怎么实现由中序和后序遍历二叉树”这篇文章的内容 香港云主机就介绍到这里，感谢各位的阅读！相信大家对“C++怎么实现由中序和后序遍历二叉树”知识都有一定的了解，大家如果还想学习更多知识，欢迎关注开发云行业资讯频道。
这篇文 香港云主机章主要介绍“Docker集群如何创建与管理”，在日常操作中，相信很多人在Docker集群如何创建与管理问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”Docker集群如何创建与管理”的疑惑有所帮助！接下来，请跟着…
免责声明：本站发布的图片视频文字，以转载和分享为主，文章观点不代表本站立场，本站不承担相关法律责任；如果涉及侵权请联系邮箱：360163164@qq.com举报，并提供相关证据，经查实将立刻删除涉嫌侵权内容。
微信扫一扫 
