- 105. Construct Binary Tree from
- [leetcode] 105. Construct Binary
- Leetcode 105. Construct Binary T
- 105. Construct Binary Tree from
- 105 Construct Binary Tree from P
- Construct Binary Tree from Preor
- LeetCode | 0105. Construct Binar
- LeetCode #1008 Construct Binary
- LeetCode #105 #106 2018-08-12
- [Leetcode]105. Construct Binary
构造树问题
已知前序遍历和中序遍历的节点顺序，来求这个树的构造。并且题目告诉，这里没有重复元素（这个条件很关键）。
用例
首先你需要知道树的三种顺序遍历：preOrder-inOrder-postOrder. 三者不同在于
- 中左右
- 左中右
- 左右中
可以看到，所谓的 pre-in-post 都是针对根节点而言的。
具体的参考 https://blog.csdn.net/qq_33243189/article/details/80222629
分析
首先你自己用手来解一遍这个用例。可以发现，你首先确定的就是根节点，因为前序第一个必然是根节点。然后中序的顺序中，可以根据根节点的位置，找到左右子树。同样在左右子树中做上面相同的事情，即可以确定整个树。
思路
迭代的思想。
- 通过前序确定根节点。
- 在中序中，根据根节点位置确定左右子树。
- 在左右子树中，迭代上面的1、2步
代码
网友评论