C++实现LeetCode(106.由中序和后序遍历建立二叉树)
[LeetCode] 106. Construct Binary Tree from Inorder and Postorder Traversal 由中序和后序遍历建立二叉树
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, given
inorder = [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。针对这道题，由于后序的顺序的最后一个肯定是根，所以原二叉树的根结点可以知道，题目中给了一个很关键的条件就是树中没有相同元素，有了这个条件就可以在中序遍历中也定位出根节点的位置，并以根节点的位置将中序遍历拆分为左右两个部分，分别对其递归调用原函数。代码如下：
class Solution {
public:
TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
return buildTree(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);
}
TreeNode *buildTree(vector<int> &inorder, int iLeft, int iRight, vector<int> &postorder, int pLeft, int pRight) {
if (iLeft > iRight || pLeft > pRight) return NULL;
TreeNode *cur = new TreeNode(postorder[pRight]);
int i = 0;
for (i = iLeft; i < inorder.size(); ++i) {
if (inorder[i] == cur->val) break;
}
cur->left = buildTree(inorder, iLeft, i - 1, postorder, pLeft, pLeft + i - iLeft - 1);
cur->right = buildTree(inorder, i + 1, iRight, postorder, pLeft + i - iLeft, pRight - 1);
return cur;
}
};
上述代码中需要小心的地方就是递归是 postorder 的左右 index 很容易写错，比如 pLeft + i - iLeft - 1, 这个又长又不好记，首先我们要记住 i - iLeft 是计算 inorder 中根节点位置和左边起始点的距离，然后再加上 postorder 左边起始点然后再减1。我们可以这样分析，如果根结点就是左边起始点的话，那么拆分的话左边序列应该为空集，此时 i - iLeft 为0， pLeft + 0 - 1 < pLeft, 那么再递归调用时就会返回 NULL, 成立。如果根节点是左边起始点紧跟的一个，那么 i - iLeft 为1， pLeft + 1 - 1 = pLeft，再递归调用时还会生成一个节点，就是 pLeft 位置上的节点，为原二叉树的一个叶节点。
下面来看一个例子, 某一二叉树的中序和后序遍历分别为：
Inorder: 11 4 5 13 8 9
Postorder: 11 4 13 9 8 5
11 4 5 13 8 9 => 5
11 4 13 9 8 5 / \
11 4 13 8 9 => 5
11 4 13 9 8 / \
4 8
11 13 9 => 5
11 13 9 / \
4 8
/ / \
11 13 9
Github 同步地址：
https://github.com/grandyang/leetcode/issues/106
类似题目：
Construct Binary Tree from Preorder and Postorder Traversal
Construct Binary Tree from Preorder and Inorder Traversal
参考资料：
https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
到此这篇关于C++实现LeetCode(106.由中序和后序遍历建立二叉树)的文章就介绍到这了,更多相关C++实现由中序和后序遍历建立二叉树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！
相关推荐
-
C++实现LeetCode(104.二叉树的最大深度)
[LeetCode] 104. Maximum Depth of Binary Tree 二叉树的最大深度 Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. Note: A leaf is a node with no child
-
C++实现LeetCode(108.将有序数组转为二叉搜索树)
[LeetCode] 108.Convert Sorted Array to Binary Search Tree 将有序数组转为二叉搜索树 Given an array where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a height-balanced binary tree is defined as a binary tree in wh
-
C++实现LeetCode(145.二叉树的后序遍历)
[LeetCode] 145. Binary Tree Postorder Traversal 二叉树的后序遍历 Given a binary tree, return the postorder traversal of its nodes' values. For example: Given binary tree {1,#,2,3}, 1 \ 2 / 3 return [3,2,1]. Note: Recursive solution is trivial, could you d
-
C++实现LeetCode(101.判断对称树)
[LeetCode] 101.Symmetric Tree 判断对称树 Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For example, this binary tree is symmetric: 1 / \ 2 2 / \ / \ 3 4 4 3 But the following is not: 1 / \ 2
-
C++实现LeetCode(103.二叉树的之字形层序遍历)
[LeetCode] 103. Binary Tree Zigzag Level Order Traversal 二叉树的之字形层序遍历 Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between). For example
-
C++实现LeetCode(102.二叉树层序遍历)
[LeetCode] 102. Binary Tree Level Order Traversal 二叉树层序遍历 Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level). For example: Given binary tree {3,9,20,#,#,15,7}, 3 / \ 9 20 / \ 15
-
C++实现LeetCode(99.复原二叉搜索树)
[LeetCode] 99. Recover Binary Search Tree 复原二叉搜索树 Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure. Example 1: Input: [1,3,null,null,2] 1 / 3 \ 2 Output: [3,1,null,null,2] 3 / 1
-
C++实现LeetCode(100.判断相同树)
[LeetCode] 100. Same Tree 判断相同树 Given two binary trees, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical and the nodes have the same value. Example 1: Input: 1
-
C++实现LeetCode(107.二叉树层序遍历之二)
[LeetCode] 107. Binary Tree Level Order Traversal II 二叉树层序遍历之二 Given the root of a binary tree, return the bottom-up level order traversal of its nodes' values. (i.e., from left to right, level by level from leaf to root). Example 1: Input: root = [3
-
C++实现LeetCode(106.由中序和后序遍历建立二叉树)
[LeetCode] 106. Construct Binary Tree from Inorder and Postorder Traversal 由中序和后序遍历建立二叉树 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, given ino
-
C++实现LeetCode(105.由先序和中序遍历建立二叉树)
[LeetCode] 105. Construct Binary Tree from Preorder and Inorder Traversal 由先序和中序遍历建立二叉树 Given preorder and inorder traversal of a tree, construct the binary tree. Note: You may assume that duplicates do not exist in the tree. For example, given preor
-
C++实现LeetCode(889.由先序和后序遍历建立二叉树)
[LeetCode] 889. Construct Binary Tree from Preorder and Postorder Traversal 由先序和后序遍历建立二叉树 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
-
JavaScript实现二叉树的先序、中序及后序遍历方法详解
本文实例讲述了JavaScript实现二叉树的先序.中序及后序遍历方法.分享给大家供大家参考,具体如下: 之前学数据结构的时候,学了二叉树的先序.中序.后序遍历的方法,并用C语言实现了,下文是用js实现二叉树的3种遍历,并以动画的形式展现出遍历的过程. 整个遍历过程还是采用递归的思想,原理很粗暴也很简单 先序遍历的函数: function preOrder(node){ if(!(node==null)){ divList.push(node); preOrder(node.firstEleme
-
Python实现树的先序、中序、后序排序算法示例
本文实例讲述了Python实现树的先序.中序.后序排序算法.分享给大家供大家参考,具体如下: #encoding=utf-8 class Tree(): def __init__(self,leftjd=0,rightjd=0,data=0): self.leftjd = leftjd self.rightjd = rightjd self.data = data class Btree(): def __init__(self,base=0): self.base = base #前序遍历 根
-
PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解
本文实例讲述了PHP实现二叉树深度优先遍历(前序.中序.后序)和广度优先遍历(层次).分享给大家供大家参考,具体如下: 前言: 深度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次.要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为先序遍历.中序遍历.后序遍历.具体说明如下: 前序遍历:根节点->左子树->右子树 中序遍历:左子树->根节点->右子树 后序遍历:左子树->右子树->根节点 广度优先遍历:又叫层次遍历,从上往下对每一层依
-
JavaScript数据结构与算法之二叉树遍历算法详解【先序、中序、后序】
本文实例讲述了JavaScript数据结构与算法之二叉树遍历算法.分享给大家供大家参考,具体如下: javascript数据结构与算法--二叉树遍历(先序) 先序遍历先访问根节点, 然后以同样方式访问左子树和右子树 代码如下: /* *二叉树中,相对较小的值保存在左节点上,较大的值保存在右节点中 * * * */ /*用来生成一个节点*/ function Node(data, left, right) { this.data = data;//节点存储的数据 this.left = left;
-
PHP基于非递归算法实现先序、中序及后序遍历二叉树操作示例
本文实例讲述了PHP基于非递归算法实现先序.中序及后序遍历二叉树操作.分享给大家供大家参考,具体如下: 概述: 二叉树遍历原理如下: 针对上图所示二叉树遍历: 1. 前序遍历:先遍历根结点,然后遍历左子树,最后遍历右子树. ABDHECFG 2.中序遍历:先遍历左子树,然后遍历根结点,最后遍历右子树. HDBEAFCG 3.后序遍历:先遍历左子树,然后遍历右子树,最后遍历根节点. HDEBFGCA 实现方法: 先序遍历:利用栈先进后出的特性,先访问根节点,再把右子树压入,再压入左子树.这样取出的
-
Java二叉搜索树遍历操作详解【前序、中序、后序、层次、广度优先遍历】
本文实例讲述了Java二叉搜索树遍历操作.分享给大家供大家参考,具体如下: 前言:在上一节Java二叉搜索树基础中,我们对树及其相关知识做了了解,对二叉搜索树做了基本的实现,下面我们继续完善我们的二叉搜索树. 对于二叉树,有深度遍历和广度遍历,深度遍历有前序.中序以及后序三种遍历方法,广度遍历即我们寻常所说的层次遍历,如图: 因为树的定义本身就是递归定义,所以对于前序.中序以及后序这三种遍历我们使用递归的方法实现,而对于广度优先遍历需要选择其他数据结构实现,本例中我们使用队列来实现广度优先遍历.
-
C语言数据结构二叉树先序、中序、后序及层次四种遍历
目录 一.图示展示 (1)先序遍历 (2)中序遍历 (3)后序遍历 (4)层次遍历 (5)口诀 二.代码展示 一.图示展示 (1)先序遍历 先序遍历可以想象为,一个小人从一棵二叉树根节点为起点,沿着二叉树外沿,逆时针走一圈回到根节点,路上遇到的元素顺序,就是先序遍历的结果 先序遍历结果为:A B D H I E J C F K G 动画演示: 记住小人沿着外围跑一圈(直到跑回根节点),多看几次动图便能理解 (2)中序遍历 中序遍历可以看成,二叉树每个节点,垂直方向投影下来(可以理解为每个节点从最