免费qq空间访客网站,设计上海展,企业网站网页设计有哪些,做个网站每年都要交域名费吗根据一棵树的前序遍历与中序遍历构造二叉树。注意:
你可以假设树中没有重复的元素。例如#xff0c;给出前序遍历 preorder [3,9,20,15,7]
中序遍历 inorder [9,3,15,20,7]
返回如下的二叉树#xff1a;3/ \9 20/ \15 7代码
/*** Definition for a binary tree node.*…根据一棵树的前序遍历与中序遍历构造二叉树。注意:
你可以假设树中没有重复的元素。例如给出前序遍历 preorder [3,9,20,15,7]
中序遍历 inorder [9,3,15,20,7]
返回如下的二叉树3/ \9 20/ \15 7
代码
/*** 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 build(preorder,0,preorder.length-1,inorder,0,inorder.length-1);}public TreeNode build(int[] preorder,int pl,int pr, int[] inorder,int il,int ir) {if(plpr||ilir) return null;//递归边界int index0;while (preorder[pl]!inorder[ilindex]) index;//找出父节点在中序遍历的位置TreeNode tempnew TreeNode(preorder[pl]);temp.leftbuild(preorder, pl1, plindex, inorder, il, ilindex-1);
//根据index和父节点将两个数组分成两半递归寻找左右子树temp.rightbuild(preorder, plindex1, pr, inorder, ilindex1, ir);return temp;}
}
