mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-06 17:44:10 +08:00
37 lines
920 B
Markdown
Executable File
37 lines
920 B
Markdown
Executable File
# [105. Construct Binary Tree from Preorder and Inorder Traversal](https://leetcode.com/problems/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
|
||
|
||
|
||
|
||
## 题目大意
|
||
|
||
根据一棵树的前序遍历与中序遍历构造二叉树。
|
||
|
||
注意:
|
||
你可以假设树中没有重复的元素。
|
||
|
||
|
||
## 解题思路
|
||
|
||
- 给出 2 个数组，根据 preorder 和 inorder 数组构造一颗树。
|
||
- 利用递归思想，从 preorder 可以得到根节点，从 inorder 中得到左子树和右子树。只剩一个节点的时候即为根节点。不断的递归直到所有的树都生成完成。
|