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

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

    3
/ \
9  20
/  \
15   7

这道题要求用先序和中序遍历来建立二叉树，跟之前那道 Construct Binary Tree from Inorder and Postorder Traversal 原理基本相同，针对这道题，由于先序的顺序的第一个肯定是根，所以原二叉树的根节点可以知道，题目中给了一个很关键的条件就是树中没有相同元素，有了这个条件就可以在中序遍历中也定位出根节点的位置，并以根节点的位置将中序遍历拆分为左右两个部分，分别对其递归调用原函数，参见代码如下：

class Solution {
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        return buildTree(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
    }
    TreeNode *buildTree(vector<int> &preorder, int pLeft, int pRight, vector<int> &inorder, int iLeft, int iRight) {
        if (pLeft > pRight || iLeft > iRight) return NULL;
        int i = 0;
        for (i = iLeft; i <= iRight; ++i) {
            if (preorder[pLeft] == inorder[i]) break;
        }
        TreeNode *cur = new TreeNode(preorder[pLeft]);
        cur->left = buildTree(preorder, pLeft + 1, pLeft + i - iLeft, inorder, iLeft, i - 1);
        cur->right = buildTree(preorder, pLeft + i - iLeft + 1, pRight, inorder, i + 1, iRight);
        return cur;
    }
};

下面来看一个例子, 某一二叉树的中序和后序遍历分别为：

Preorder:　  　5　　4　　11　　8　　13　　9

Inorder:　　 　11　　4　　5　　13　　8　　9

5　　4　　11　　8　　13　　9　　　　　　=>　　　　　　　　　 5

11　　4　　5　　13　　8　　9　　　　　　　　　　　　　　　　/　　\

4　　11　　 　　8　　 13　　9　　　　　　=>　　　　　　　　　5

11　　4　　　　 13　　8　　9　　 　　　　　　　　　　　　　  /　　\

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　4　　　8

11　　　　 　　13　　　　9　　　　　　　　=>　　　　　　　　　5

11　　　　　　 13　　　　9　　　　 　　　　　　　　　　　　   /　　\

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　4　　　8

　　　　　　　　　　　　　　　　　　　　　　　　　　　　/　　　 /     \

　　　　　　　　　　　　　　　　　　　　　　　　　　　11　　  13　　  9

做完这道题后，大多人可能会有个疑问，怎么没有由先序和后序遍历建立二叉树呢，这是因为先序和后序遍历不能唯一的确定一个二叉树，比如下面五棵树：

1　　　　　　preorder:　　  1　　2　　3
/ \　　　　　  inorder:　　     2　　1　　3
2 3　　  　　 postorder:　　 2　　3　　1

1   　　　　preorder:　　   1　　2　　3
/ 　　　　　 inorder:　　     3　　2　　1
2 　　　　     postorder: 　　3　　2　　1
/
3

1　　　　    preorder:　　  1　　2　　3
/ 　　　　　  inorder:　　    2　　3　　1
2 　　　　　　postorder:　　3　　2　　1
\
3

       1　　　　     preorder:　　  1　　2　　3
\ 　　　　   inorder:　　    1　　3　　2
2 　　　　 postorder:　　3　　2　　1
/
3

       1　　　　     preorder:　　  1　　2　　3
\ 　　　　　inorder:　　    1　　2　　3
2 　　　　 postorder:　　3　　2　　1
\
3

从上面我们可以看出，对于先序遍历都为 1 2 3 的五棵二叉树，它们的中序遍历都不相同，而它们的后序遍历却有相同的，所以只有和中序遍历一起才能唯一的确定一棵二叉树。但可能会有小伙伴指出，那第 889 题 Construct Binary Tree from Preorder and Postorder Traversal 不就是从先序和后序重建二叉树么？难道博主被啪啪打脸了么？难道博主的一世英名就此毁于一旦了么？不，博主向命运的不公说不，请仔细看那道题的要求 "Return any binary tree that matches the given preorder and postorder traversals."，是让返回任意一棵二叉树即可，所以这跟博主的结论并不矛盾。长舒一口气，博主的晚节保住了～

Github 同步地址：

https://github.com/grandyang/leetcode/issues/105

类似题目：

Construct Binary Tree from Inorder and Postorder Traversal

Construct Binary Tree from Preorder and Postorder Traversal

参考资料：

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/discuss/34538/My-Accepted-Java-Solution

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/discuss/34562/Sharing-my-straightforward-recursive-solution

到此这篇关于C++实现LeetCode(105.由先序和中序遍历建立二叉树)的文章就介绍到这了,更多相关C++实现由先序和中序遍历建立二叉树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(107.二叉树层序遍历之二)

    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(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(98.验证二叉搜索树)

    [LeetCode] 98. Validate Binary Search Tree 验证二叉搜索树 Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node's key. The ri

  • C++实现LeetCode(139.拆分词句)

    [LeetCode] 139. Word Break 拆分词句 Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. Note: The same word in the dic

  • 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(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(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(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

  • 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

  • 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 #前序遍历 根

  • C++基于先序、中序遍历结果重建二叉树的方法

    本文实例讲述了C++基于先序.中序遍历结果重建二叉树的方法.分享给大家供大家参考,具体如下: 题目: 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树.假设输入的前序遍历和中序遍历的结果中都不含重复的数字.例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回. 实现代码: #include <iostream> #include <vector> #include <stack> using

  • JavaScript数据结构与算法之二叉树遍历算法详解【先序、中序、后序】

    JavaScript数据结构与算法之二叉树遍历算法详解【先序、中序、后序】

    本文实例讲述了JavaScript数据结构与算法之二叉树遍历算法.分享给大家供大家参考,具体如下: javascript数据结构与算法--二叉树遍历(先序) 先序遍历先访问根节点, 然后以同样方式访问左子树和右子树 代码如下: /* *二叉树中,相对较小的值保存在左节点上,较大的值保存在右节点中 * * * */ /*用来生成一个节点*/ function Node(data, left, right) { this.data = data;//节点存储的数据 this.left = left;

  • Python实现输入二叉树的先序和中序遍历，再输出后序遍历操作示例

    本文实例讲述了Python实现输入二叉树的先序和中序遍历,再输出后序遍历操作.分享给大家供大家参考,具体如下: 实现一个功能: 输入:一颗二叉树的先序和中序遍历     输出:后续遍历 思想: 先序遍历中,第一个元素是树根     在中序遍历中找到树根,左边的是左子树 右边的是右子树 Python代码: # -*- coding:utf-8 -*- def fromFMtoL( mid ): global las #全局后序遍历 global fir #先序遍历 root = fir[0] #取

  • PHP基于非递归算法实现先序、中序及后序遍历二叉树操作示例

    本文实例讲述了PHP基于非递归算法实现先序.中序及后序遍历二叉树操作.分享给大家供大家参考,具体如下: 概述: 二叉树遍历原理如下: 针对上图所示二叉树遍历: 1. 前序遍历:先遍历根结点,然后遍历左子树,最后遍历右子树. ABDHECFG 2.中序遍历:先遍历左子树,然后遍历根结点,最后遍历右子树. HDBEAFCG 3.后序遍历:先遍历左子树,然后遍历右子树,最后遍历根节点. HDEBFGCA 实现方法: 先序遍历:利用栈先进后出的特性,先访问根节点,再把右子树压入,再压入左子树.这样取出的

  • C语言数据结构二叉树先序、中序、后序及层次四种遍历

    C语言数据结构二叉树先序、中序、后序及层次四种遍历

    目录 一.图示展示 (1)先序遍历 (2)中序遍历 (3)后序遍历 (4)层次遍历 (5)口诀 二.代码展示 一.图示展示 (1)先序遍历 先序遍历可以想象为,一个小人从一棵二叉树根节点为起点,沿着二叉树外沿,逆时针走一圈回到根节点,路上遇到的元素顺序,就是先序遍历的结果 先序遍历结果为:A B D H I E J C F K G 动画演示: 记住小人沿着外围跑一圈(直到跑回根节点),多看几次动图便能理解 (2)中序遍历 中序遍历可以看成,二叉树每个节点,垂直方向投影下来(可以理解为每个节点从最

随机推荐