题目描述
题目链接:105. Construct Binary Tree from Preorder and Inorder Traversal
Given preorder and inorder traversal of a tree, construct the binary tree.
例子
见题目描述
Follow Up
Note
You may assume that duplicates do not exist in the tree.
解题思路
这道题首先要清楚 inorder 和 preorder 两种遍历方式的特点,如下:
- inorder:根节点 ——> 左子树 ——> 右子树,所以给定一个二叉树的 inorder 顺序遍历结果,可以知道第一个节点是根节点
- preorder:左子树 ——> 根节点 ——> 右子树,所以给定一个二叉树的 preorder 顺序便利结果,假如可以知道根节点的位置,那么根节点左侧节点全为左子树,根节点右侧节点全为右子树
不难发现,inorder 遍历很容易可以找到根节点,但左右子树不好区分;而 preorder 有办法区分左右子树,但需要知道根节点的位置。因此结合一下,我们可以用哈希表先存储 preorder 中所有值的位置,再通过 inorder 中第一个元素找到根节点值,然后就可以在 preorder 中找到根节点位置,从而区分左右子树各自的区间长度,在知道区间长度之后我们可以 inorder 中按长度划分左右子树,接下来只需要对左右子树重复递归操作即可,代码如下:
1 | /** |
- 时间复杂度: O(n)
- 空间复杂度: O(n)
GitHub 代码同步地址: 105.ConstructBinaryTreeFromPreorderAndInorderTraversal.cpp
其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions