LeetCode(105)-Construct Binary Tree from Preorder and Inorder Traversal
程序员文章站
2022-03-15 11:03:11
...
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
这道题要求用先序和中序遍历来建立二叉树
我们下面来看一个例子, 某一二叉树的前序和中序遍历分别为:
Preorder: 5 4 11 8 13 9
Inorder: 11 4 5 13 8 9
public class l105_pre_and_inorder {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if((preorder == null) ||(inorder == null) ||( preorder.length == 0 )|| (inorder.length == 0)) {
return null;
}
return build(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
}
public TreeNode build(int[] preorder,int prestart,int preend,int[] inorder,int instart,int inend){
if(prestart>preend||instart>inend){
return null;
}
int value=preorder[prestart];
TreeNode root=new TreeNode(value);
int index=0;
for(int i=instart;i<=inend;i++){
if(inorder[i]==value){
index=i;
}
}
root.left=build(preorder,prestart+1,prestart+index-instart,inorder,instart,index-1);
root.right=build(preorder,prestart+index-instart+1,preend,inorder,index+1,inend);
return root;
}
}
推荐阅读
-
LeetCode 105 Construct Binary Tree from Preorder and Inorder Traversal
-
LeetCode: 105. Construct Binary Tree from Preorder and Inorder Traversal
-
leetcode 随笔 Construct Binary Tree from Preorder and Inorder Traversal
-
105. Construct Binary Tree from Preorder and Inorder Traversal
-
Construct Binary Tree from Preorder and Inorder Traversal
-
Construct Binary Tree from Preorder and Inorder Traversal
-
LeetCode(106)Construct Binary Tree from Inorder and Postorder Traversal
-
LeetCode 94. Binary Tree Inorder Traversal
-
105. Construct Binary Tree from Preorder and Inorder Traversal
-
LeetCode106. Construct Binary Tree from Inorder and Postorder Traversal