上海专业做网站电话,wordpress 微信采集插件,烟台网站建设托管,南京建站公司模板跟着carl学算法#xff0c;本系列博客仅做个人记录#xff0c;建议大家都去看carl本人的博客#xff0c;写的真的很好的#xff01; 代码随想录 LeetCode#xff1a;106.从中序与后序遍历序列构造二叉树 给定两个整数数组 inorder 和 postorder #xff0c;其中 inorder … 跟着carl学算法本系列博客仅做个人记录建议大家都去看carl本人的博客写的真的很好的 代码随想录 LeetCode106.从中序与后序遍历序列构造二叉树 给定两个整数数组 inorder 和 postorder 其中 inorder 是二叉树的中序遍历 postorder 是同一棵树的后序遍历请你构造并返回这颗 二叉树 。 示例 1: 输入inorder [9,3,15,20,7], postorder [9,15,7,20,3] 输出[3,9,20,null,null,15,7] 示例 2: 输入inorder [-1], postorder [-1] 输出[-1] 需要注意这里数组的位置都是左闭右开的前中后中都能唯一确定一颗二叉树前后不行前和后单独的都能确定根节点但是无法区分出左右子树的节点 public TreeNode buildTree(int[] inorder, int[] postorder) {if (inorder.length 0 || postorder.length 0)return null;return buildHelper(inorder, 0, inorder.length, postorder, 0, postorder.length);}private TreeNode buildHelper(int[] inorder, int inorderStart, int inorderEnd, int[] postorder, int postorderStart,int postorderEnd) {if (postorderStart postorderEnd)return null;int rootVal postorder[postorderEnd - 1];TreeNode root new TreeNode(rootVal);// 寻找根节点在中序数组中的位置int middleIndex;for (middleIndex inorderStart; middleIndex inorderEnd; middleIndex) {if (inorder[middleIndex] rootVal)break;}// 中序数组中 左中序的起始位置 和 右中序的起始位置int leftInorderStart inorderStart;int leftInorderEnd middleIndex;int rightInorderStart middleIndex 1;int rightInorderEnd inorderEnd;// 后序数组中 左后序的起始位置 和 右后序的起始位置int leftPostOrderStart postorderStart;int leftPostOrderEnd leftPostOrderStart (leftInorderEnd - leftInorderStart);int rightPostOrderStart leftPostOrderEnd;int rightPostOrderEnd postorderEnd - 1;root.left buildHelper(inorder, leftInorderStart, leftInorderEnd, postorder, leftPostOrderStart,leftPostOrderEnd);root.right buildHelper(inorder, rightInorderStart, rightInorderEnd, postorder, rightPostOrderStart,rightPostOrderEnd);return root;}
