做网站用什么,小红书手工,网络公司网络营销推广方案,网站公司利润根据一棵树的前序遍历与中序遍历构造二叉树。注意:
你可以假设树中没有重复的元素。例如#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;}
}
