LeetCode 106: 从中序与后序遍历序列构造二叉树

题目:

Given inorder and postorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

```中序遍历 inorder = [9,3,15,20,7]

```

```    3
/ \
9  20
/  \
15   7
```

解题思路:

• 前序遍历：根结点 -> 左子结点 -> 右子结点
• 中序遍历：左子结点 -> 根结点 -> 右子结点
• 后序遍历：右子结点 -> 左子结点 -> 根结点

```    3
/ \
9  20
/  \
15   7
```
```前序遍历 preorder = [3,9,20,15,7]

```

```中序遍历 inorder = [9,3,15,20,7]
^

3
/ \
[9]  [15,20,7]
```

```中序遍历 inorder ：
3
/ \
[9] [15,20,7]
^

3
/ \
[9] 20
/  \
[15] [7]
```

```中序遍历 inorder ：
3
/ \
[9] 20
/  \
[15] [7]
^

3
/ \
[9] 20
/  \
[15]  7
```

……

递归解法:

Java:

```class Solution {
int[] postorder;
int[] inorder;
int index_post;
HashMap<Integer, Integer> index_map = new HashMap<>();

private TreeNode helper(int left, int right) {
// 基线条件
if (left > right)
return null;
// 按逆序逐个取后序遍历结果，并构造为根结点
int root_val = postorder[index_post--];
TreeNode root = new TreeNode(root_val);
// 查找该根结点在中序遍历中的索引位置
int index_in = index_map.get(root_val);
// 构造递归
root.right = helper(index_in + 1, right);
root.left = helper(left, index_in - 1);
return root;
}
public TreeNode buildTree(final int[] inorder, final int[] postorder) {
this.inorder = inorder;
this.postorder = postorder;
this.index_post = postorder.length - 1;
// 将中序遍历结果的结点值与索引位置映射
for (int i = 0; i < inorder.length; i++)
index_map.put(inorder[i], i);
return helper(0, inorder.length - 1);
}
}
```

Python:

```class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
def helper(left=0, right=len(inorder)-1) -> TreeNode:
nonlocal index_post
# 基线条件
if left > right:
return None
# 按逆序逐个取后序遍历结果，并构造为根结点
root_val = postorder[index_post]
root = TreeNode(root_val)
# 查找该根结点在中序遍历中的索引位置
index_in = index_map[root_val]
# 构造递归
index_post -= 1
root.right = helper(index_in+1, right)
root.left = helper(left, index_in-1)
return root

index_post = len(inorder)-1
# 将后序遍历结果的结点值与索引位置映射
index_map = {val: index for index, val in enumerate(inorder)}
return helper()
```

0 条评论

• 【Leetcode】106. 从中序与后序遍历序列构造二叉树

中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3] 返回如下的二叉树：

• 每天一道leetcode-106从中序与后序遍历序列构造二叉树

中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3]

• Leetcode No.106 从中序与后序遍历序列构造二叉树

中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3] 返回如下的二叉树：

• ​LeetCode刷题实战106：从中序与后序遍历序列构造二叉树

https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorde...

• 【LeetCode系列】从中序与后序遍历序列构造二叉树 & 从前序与中序遍历序列构造二叉树

前序遍历是根左右，因此preorder第一个元素一定是整个树的根。由于题目说明了没有重复元素，因此我们可以通过preorder[0]去inorder找到根在in...

• [Leetcode][python]从前序与中序遍历序列构造二叉树/从中序与后序遍历序列构造二叉树

根据二叉树的前序遍历和中序遍历（ 中序和后序）结果生成二叉树 假设没有重复数字

• LeetCode 0106. 从中序与后序遍历序列构造二叉树

非常非常典型的题目，首先解决这道题我们需要明确给定一棵二叉树，我们是如何对其进行中序遍历与后序遍历的：

• 【Leetcode】105. 从前序与中序遍历序列构造二叉树

前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树：

• LeetCode 105: 从前序与中序遍历序列构造二叉树

Given preorder and inorder traversal of a tree, construct the binary tree.

• leetcode 105. 从前序与中序遍历序列构造二叉树

思路分析: 二叉树相关的很多问题的解决思路都有分治法的思想在里面。我们复习一下分治法的思想：把原问题拆解成若干个与原问题结构相同但规模更小的子问题，待子问题解...

• Leetcode No.105 从前序与中序遍历序列构造二叉树

前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树：

• 105. 从前序与中序遍历序列构造二叉树

前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树：

• LC105-从前序与中序遍历序列构造二叉树

可以将中序遍历得值合索引存在一个哈希表中,这样就可以找到根节点在中序遍历数组中的索引

• 105.从前序与中序遍历序列构造二叉树

给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。

• Leetcode|二叉树的修改与构造|从前中|后中|前后遍历序列构造二叉树

由于每次要重新在inorder中从left到right顺序搜索与根节点相同值的索引，因此，对于海量数据的中序inorder向量，查值效率不是最高。

• 力扣105——从前序与中序遍历序列构造二叉树

原题url：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-i...

• ​LeetCode刷题实战105：从前序与中序遍历序列构造二叉树

https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/