苏州网站建设制作,十款看免费行情的软件,做幼儿英语的教案网站,顺义区专业网站制作网站建设2024.2.22 题目来源我的题解方法一 分治思想 题目来源
力扣每日一题#xff1b;题序#xff1a;889
我的题解
方法一 分治思想 题解参考#xff1a;官方题解 令 nn为二叉树的节点数目#xff0c;那么根据前序遍历与后序遍历的定义#xff0c;preorder[0] 与 postorder[… 2024.2.22 题目来源我的题解方法一 分治思想 题目来源
力扣每日一题题序889
我的题解
方法一 分治思想 题解参考官方题解 令 nn为二叉树的节点数目那么根据前序遍历与后序遍历的定义preorder[0] 与 postorder[n−1] 都对应二叉树的根节点。获取根节点后需要划分根节点的左子树与右子树考虑两种情况 原二叉树的根节点的左子树不为空那么 preorder[1]对应左子树的根节点原二叉树的根节点的左子树为空那么 preorder[1] 对应右子树的根节点。 对于以上两种情况无法区分 preorder[1]到底是哪种情况。但是对于第二种情况将原二叉树的右子树移到左子树后得到的二叉树的前序遍历数组与后序遍历数组与原二叉树相同所以只需要考虑第一种情况。因为二叉树的值互不相同可以在 postorder 中找到 postorder[k]preorder[1]那么左子树的节点数目为 k1。基于此可以对 preorder 和 postorder进行分治处理即将 preorder 划分为根节点、左子树节点和右子树节点三个部分postorder也划分为左子树节点、右子树节点和根节点三个部分。那么问题划分为 根据左子树节点的前序遍历与后序遍历数组构造二叉树根据右子树节点的前序遍历与后序遍历数组构造二叉树。 同时当节点数目为 1 时对应构造的二叉树只有一个节点。可以递归地对问题进行求解就可得到构造的二叉树。 时间复杂度O(n) 空间复杂度O(n) public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {MapInteger,Integer mapnew HashMap();//为了减少遍历后序序列使用哈希表存储for(int i0;ipostorder.length;i){map.put(postorder[i],i);}return createTree(preorder,postorder,0,preorder.length-1,0,postorder.length-1,map);}
public TreeNode createTree(int[] preorder,int[] postorder,int preL,int preR,int postL,int postR,MapInteger,Integer map){if(preLpreR||postLpostR)return null;if(preLpreR)return new TreeNode(preorder[preL]);int valpreorder[preL];//下一个在前序中的根节点在后序中的位置int indexmap.get(preorder[preL1]);//左子树的节点数int leftindex-postL1;TreeNode rootnew TreeNode(val);root.leftcreateTree(preorder,postorder,preL1,preLleft,postL,index,map);root.rightcreateTree(preorder,postorder,preLleft1,preR,index1,postR-1,map);return root;
}有任何问题欢迎评论区交流欢迎评论区提供其它解题思路代码也可以点个赞支持一下作者哈~
