找网站做任务领q币,做设备出口网站,怎么做网站推广怀化,工信部做网站认证吗给定两个整数数组 inorder 和 postorder #xff0c;其中 inorder 是二叉树的中序遍历#xff0c; postorder 是同一棵树的后序遍历#xff0c;请你构造并返回这颗 二叉树 。 示例 1: 输入#xff1a;inorder [9,3,15,20,7], postorder [9,15,7,20,3]
输出#xff1a;[3…给定两个整数数组 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]提示:
1 inorder.length 3000postorder.length inorder.length-3000 inorder[i], postorder[i] 3000inorder 和 postorder 都由 不同 的值组成postorder 中每一个值都在 inorder 中inorder 保证是树的中序遍历postorder 保证是树的后序遍历 TreeNode *traversal(vectorint inorder, vectorint postorder) {//如果后子树为空则直接返回if (postorder.size() 0) return nullptr;//1.先确定后子树当中的根节点int rootValue postorder[postorder.size() - 1];//2,根据后结点取出来作为根结点的值TreeNode *root new TreeNode(rootValue);//3.如果它是叶子直接则直接返回if (postorder.size() 1) return root;//4.找切割点int delimiterIndex;for (delimiterIndex 0; delimiterIndex inorder.size(); delimiterIndex) {if (inorder[delimiterIndex] rootValue) break;}//切割中序数组得到 中序左数组和中序右数组vectorint leftInorder(inorder.begin(), inorder.begin() delimiterIndex);// [delimiterIndex 1, end)vectorint rightInorder(inorder.begin() delimiterIndex 1, inorder.end());//去除后子树中的最后一个结点postorder.resize(postorder.size() - 1);//切割后序数组得到 后序左数组和后序右数组vectorint leftPostorder(postorder.begin(), postorder.begin() leftInorder.size());// [delimiterIndex 1, end)vectorint rightPostorder(postorder.begin() leftInorder.size(), postorder.end());//最后组合数组并合root-left traversal(leftInorder, leftPostorder);root-right traversal(rightInorder, rightPostorder);return root;}TreeNode *buildTree(vectorint inorder, vectorint postorder) {if (inorder.size() 0 || postorder.size() 0) return NULL;return traversal(inorder, postorder);}
