长沙鞋网站建设,wordpress适合手机,wordpress自动视频播放器代码,wordpress 代码 视频文章目录 题目方法一#xff1a;递归 题目 方法一#xff1a;递归
preorder [3,9,20,15,7]
inorder [9,3,15,20,7]
首先根据 preorder 找到根节点是 3然后根据根节点将 inorder 分成左子树和右子树
左子树
inorder [9]右子树
inorder [15,20,7]这时候3是根节点
3的左子树… 文章目录 题目方法一递归 题目 方法一递归
preorder [3,9,20,15,7]
inorder [9,3,15,20,7]
首先根据 preorder 找到根节点是 3然后根据根节点将 inorder 分成左子树和右子树
左子树
inorder [9]右子树
inorder [15,20,7]这时候3是根节点
3的左子树为如下
preorder[9] 3的右子树为如下preorder[20 15 7] 现在我们只需要构造左子树和右子树即可成功把大问题化成了小问题
然后重复上边的步骤继续划分直到 preorder 空返回 null 即可
解题的关键在与找根节点和 左子树和右子树在前序遍历数组的范围一步步找出根节点然后划分出左右子树然后让根节点指向左右子树然后又对左右子树左重复动作
这个根据前序遍历的第一个节点根节点去中序遍历中找左右子树的范围可以根据前序遍历的根节点值循环去中序遍历中找因为题目保证节点不存在重复所以可以根据中序遍历维护一个节点和下标的哈希表这个前序遍历的根节点可以轻松的找到中序遍历的根节点从而在前序遍历中确定左右子树的范围
根据中序遍历维护一个key为节点value为下标的哈希表根据前序遍历的第一个节点也就是根节点去中序遍历哈希表找根节点再根据哈希表中找到的根节点在中序遍历找到左子树的区间再根据这个区间去前序遍历找到左子树的范围以及右子树的范围新建根节点指向待处理的左子树和右子树递归 // 方法一 递归哈希(到中序遍历数组中找 根节点值 然后判断出左右子树再根据前序构建树)MapInteger,Integer inorderMap new HashMap(); //记录中序遍历节点与数组下标的映射关系public TreeNode buildTree(int[] preorder, int[] inorder) {//中序遍历数组下标映射map构造for(int i 0 ; iinorder.length;i){inorderMap.put(inorder[i],i);}//构建树 前序数组 前序数组起始位置 前序数组末尾位置 中序数组起始位置 return myBuildTree(preorder, 0, preorder.length - 1, 0 );}public TreeNode myBuildTree(int[] preorder, int prebegin , int preend,int inbegin) {if ( prebegin preend) {return null;}int preorder_root prebegin; // 前序遍历中的第一个节点就是根节点int preindex inorderMap.get(preorder[preorder_root]); // 在中序遍历中定位根节点TreeNode root new TreeNode(preorder[preorder_root]); // 先把根节点建立出来int size_left_subtree preindex - 1 -inbegin; // 得到左子树中的节点数目// 递归地构造左子树并连接到根节点// 先序遍历中「从 左边界1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素root.left myBuildTree(preorder,prebegin 1,prebegin1 size_left_subtree,inbegin);// 递归地构造右子树并连接到根节点// 先序遍历中「从 左边界1左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位1 到 右边界」的元素root.right myBuildTree(preorder,prebegin1 size_left_subtree1,preend,preindex1);return root;}
