保定网站建设咨询,哪个网站的域名到期直接注册,为什么要网站备案,广州建外贸网站公司简介题目
输入某二叉树的前序遍历和中序遍历的结果#xff0c;请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 示例 1: Input: preorder [3,9,20,15,7], inorder [9,3,15,20,7]Output: [3,9,20,null,null,15,7] 示例 2: Input: preo…题目
输入某二叉树的前序遍历和中序遍历的结果请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 示例 1: Input: preorder [3,9,20,15,7], inorder [9,3,15,20,7]Output: [3,9,20,null,null,15,7] 示例 2: Input: preorder [-1], inorder [-1]Output: [-1] 限制
0 节点个数 5000 解题思路 1.题目要求我们利用前序遍历和中序遍历构建出二叉树我们可以画图来理解一下 举个例子 根据我们对数据结构中二叉树部分的学习我们知道前序遍历是根左右所以第一个元素一定是这颗二叉树的根。 那么中序遍历是左右根所以数字 3 左边的是它的左子树部分右边的是他的右子树部分。 设 3 在数组 inorder中的下标为 i 前序遍历左子树部分 [ l1 1, l1 (i - l2) ] 右子树部分 [l2, i - 1] 中序遍历左子树部分 [l1 (i - l2) 1, r1] 右子树部分[i 1, r2] 我们按照这个思想继续处理 3 的左子树和右子树 也就是进行递归操作 3 的左子树中 9 为根节点那么 5 和 6 为 9 的左右子树3 的右子树中 20 为根节点15 和7 为 3 的左右子树。最终生成的数如下图所示 2.代码部分首先我们判断所给数组是否为空若为空直接返回 null然后我们新建一个map 用于存储inorder数组的下标和对应的值方便我们后序对 root 所对应的数组下标进行查找。 然后我们让root f( ) 函数。 3.f( ) 函数的作用是利用传入的前序遍历和中序遍历的数组找到二叉树的 root 节点并将数组划分为 root 节点的左右子树。结束条件为 r1 l1 r2 l2。处理完成后返回 root 即可。 代码实现
class Solution {MapInteger,Integer map new HashMap();public TreeNode buildTree(int[] preorder, int[] inorder) {if(preorder null || preorder.length 0){return null;}for(int i 0; i inorder.length; i){map.put(inorder[i],i);}TreeNode root f(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);return root;}public TreeNode f(int[] preorder, int l1, int r1, int[] inorder, int l2, int r2){if(r1 l1 r2 l2){return null;}TreeNode root new TreeNode(preorder[l1]);int i map.get(preorder[l1]);root.left f(preorder, l1 1, l1 (i - l2), inorder, l2, i - 1);root.right f(preorder,l1 (i - l2) 1, r1, inorder, i 1, r2);return root;}
}
测试结果
