105、 从前序与中序遍历序列构造二叉树
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
- 前序遍历
preorder = [3,9,20,15,7] - 中序遍历
inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
题解
1、二分递归构建
从前序遍历中找到根节点，在从中序遍历中找到左右子树区间
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildBTree(preorder,inorder,0,preorder.length - 1,0,inorder.length -1);
}
private TreeNode buildBTree(int[] preorder,int[] inorder,int pl,int pr,int il,int ir) {
// 退出递归
if (pl > pr || il > ir) {
return null;
}
// 按照前序遍历 在中序遍历中 找到匹配的元素 将
int rootVal = preorder[pl];
int rootPos = 0;
for (int i = il;i <= ir;i++) {
if (inorder[i] == rootVal) {
rootPos = i;
break;
}
}
TreeNode root = new TreeNode(rootVal);
// rootPos = 1
// 递归构建左右子树
root.left = buildBTree(preorder,inorder,pl+1,pl+rootPos-il,il,rootPos);
root.right = buildBTree(preorder,inorder,pl+rootPos-il+1,pr,rootPos+1,ir);
// 返回根节点
return root;
}
}
2、迭代法
借用栈存储前序遍历的元素，后序遍历用一个index维护。
思路类似于二叉树的迭代法中序遍历！！！
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
// 特殊情况
if (preorder == null || preorfer,length == 0) {
return null;
}
// 创建根节点
TreenNode root = new TreeNode(preorder[0]);
// 辅助栈
Stack<TreeNode> stack = new Stack<TreeNode>();
// 存放根节点
stack.push(root);
// 中序遍历指针
int inorderIndex = 0;
for (int i = 1;i < preorder.length;i++) {
// 获取前序遍历的元素，根节点右边分别为 左子树 右子树
int preorderVal = preorder[i];
// 获取当前根节点
TreeNode node = stack.peek();
// 中序遍历的当前元素不是根节点，说明存在左子树
if (node.val != inorder[inorderIndex]) {
// 构建左子树
node.left = new TreeNode(preorderVal);
// 左子树入栈
stack.push(node.left);
} else {
// 没有左子树了，构建右子树
while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
node.stack.pop();// 左子树根节点出栈
inorderIndex++;// 指针后移
}
// 构建右子树
node.right = new TreeNode(preorderVal);
// 右子树入栈
stack.push(node.right);
}
}
return root; // 返回根节点
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
