从中序与后序遍历序列构造二叉树
程序员文章站
2022-04-27 11:35:38
...
从中序与后序遍历序列构造二叉树:
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:你可以假设树中没有重复的元素。
例如,
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树:
3
/ \
9 20
/ \
15 7
分析:
根据前序和中序可以构造一颗二叉树,根据中序和后续也可以构建一颗二叉树。
反正必须要有中序才能构建,因为没有中序,你没办法确定树的形状。
例如:
先序为:[1, 2]
后序为:[2, 1]
可以构建如下
1
/
2
1
\
2
主要是使用递归构建左子树和右子树
实现代码:
// 构建二叉树,中序遍历和后序遍历
// 中序遍历 inorder = [9,3,15,20,7]
// 后序遍历 postorder = [9,15,7,20,3]
public TreeNode buildTree(int[] inorder, int[] postorder) {
return helper(inorder, postorder, postorder.length - 1, 0, inorder.length - 1);
}
//postEnd后序遍历数组长度,inStart中序遍历起始位置,inEnd中序遍历长度
//每次遍历中序是为了找到子树根节点的位置,然后通过后序找到根的左右子树根节点
public TreeNode helper(int[] inorder, int[] postorder, int postEnd, int inStart, int inEnd) {
if (inStart > inEnd) {
return null;
}
int currentVal = postorder[postEnd];//后序遍历最后一个节点为整棵树的根节点
TreeNode current = new TreeNode(currentVal);
int inIndex = 0;
for (int i = inStart; i <= inEnd; i++) {//在中序遍历中找到根节点,并记录位置,左边的为左子树,右边为右子树
if (inorder[i] == currentVal) {
inIndex = i;
}
}
// 树的左节点为,从中序中找到根节点后,左侧为左子树,遍历中序根节点左边的(从0至根节点左边第一个),后序遍历中总长度减去右子树长度和根节点长度就是右节点位置
TreeNode left = helper(inorder, postorder, postEnd - (inEnd- inIndex) - 1, inStart, inIndex - 1);
// 树的右节点为,从中序中找到根节点后,右侧为右子树,遍历中序根节点右边的(根节点直至最后),后序遍历中根节点左边第一个就是右节点
TreeNode right = helper(inorder, postorder, postEnd - 1, inIndex + 1, inEnd);
current.left = left;
current.right = right;
return current;
}
上一篇: HDU6400 Parentheses Matrix(2018HDU多校联赛第八场,构造)
下一篇: Construct Binary Tree from Inorder and Postorder Traversal
推荐阅读
-
树与二叉树 树二叉树前序、中序、后序遍历先根遍历后根遍历
-
从前序与中序遍历序列构造二叉树-二叉树
-
JavaScript数据结构与算法之二叉树遍历算法详解【先序、中序、后序】
-
Java实现二叉树先序、中序、后序遍历(递归与非递归)及层次遍历
-
JAVA 实现二叉树建立和先序,中序和后序遍历(递归与非递归)
-
java实现二叉树的前序、中序、后序、层次遍历,递归与非递归
-
二叉树递归与非递归的先序,中序,后序遍历以及层序遍历
-
LeetCode 105. 从前序与中序遍历序列构造二叉树(各种遍历二叉树的性质,递归建树)
-
LeetCode 106. 从中序与后序遍历序列构造二叉树(二叉树基础之树的重建)
-
由中序与后序遍历得到二叉树