c/c++开发分享C++实现LeetCode(105.由先序和中序遍历建立二叉树)

[leetcode] 105. construct binary tree from preorder and inorder traversal 由先序和中序遍历建立二叉树given preorde


[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 同步地址:

类似题目:

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/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++实现由先序和中序遍历建立二叉树内容请搜索<猴子技术宅>以前的文章或继续浏览下面的相关文章希望大家以后多多支持<猴子技术宅>!

需要了解更多c/c++开发分享C++实现LeetCode(105.由先序和中序遍历建立二叉树),都可以关注C/C++技术分享栏目—猴子技术宅(www.ssfiction.com)

本文来自网络收集,不代表猴子技术宅立场,如涉及侵权请点击右边联系管理员删除。

如若转载,请注明出处:https://www.ssfiction.com/c-cyuyankaifa/676113.html

发表评论

邮箱地址不会被公开。 必填项已用*标注