wordpress主题,sem优化系统,网站建设的审批,wordpress 添加编辑器提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、力扣654. 最大二叉树二、力扣105. 从前序与中序遍历序列构造二叉树三、力扣106. 从中序与后序遍历序列构造二叉树四、力扣889. 根据前序和后序遍历构造二叉… 提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档 文章目录 前言一、力扣654. 最大二叉树二、力扣105. 从前序与中序遍历序列构造二叉树三、力扣106. 从中序与后序遍历序列构造二叉树四、力扣889. 根据前序和后序遍历构造二叉树 前言
二叉树解题的思维模式分两类 1、是否可以通过遍历一遍二叉树得到答案如果可以用一个 traverse 函数配合外部变量来实现这叫「遍历」的思维模式。 2、是否可以定义一个递归函数通过子问题子树的答案推导出原问题的答案如果可以写出这个递归函数的定义并充分利用这个函数的返回值这叫「分解问题」的思维模式。 无论使用哪种思维模式你都需要思考 如果单独抽出一个二叉树节点它需要做什么事情需要在什么时候前/中/后序位置做其他的节点不用你操心递归函数会帮你在所有节点上执行相同的操作。
一、力扣654. 最大二叉树
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {return fun(nums, 0, nums.length-1);}public TreeNode fun(int[] nums, int low, int high){if(low high){return null;}int index low;for(int i low1; i high; i ){if(nums[i] nums[index]){index i;}}TreeNode cur new TreeNode(nums[index]);TreeNode l fun(nums,low,index-1);TreeNode r fun(nums,index1,high);cur.left l;cur.right r;return cur;}
}二、力扣105. 从前序与中序遍历序列构造二叉树
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {return fun(preorder, inorder, 0, preorder.length-1, 0, inorder.length-1);}public TreeNode fun(int[] preorder, int[] inorder, int preLeft,int preRight,int inPre,int inRight){if(preLeft preRight || inPre inRight){return null;}TreeNode root new TreeNode(preorder[preLeft]);int len 0;for(int i inPre; i inRight; i ){if(inorder[i] preorder[preLeft]){len i - inPre;break;}}root.left fun(preorder, inorder, preLeft1, preLeftlen, inPre, inPrelen-1);root.right fun(preorder, inorder, preLeftlen1,preRight, inPrelen1,inRight);return root;}
}三、力扣106. 从中序与后序遍历序列构造二叉树
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {MapInteger,Integer invail;public TreeNode buildTree(int[] inorder, int[] postorder) {invail new HashMap();for(int i 0; i inorder.length; i ){invail.put(inorder[i],i);}return fun(inorder, postorder, 0, postorder.length-1,0,inorder.length-1);}public TreeNode fun(int[] inorder, int[] postorder, int postLeft, int postRight, int inLeft, int inRight){if(postLeft postRight || inLeft inRight){return null;}TreeNode root new TreeNode(postorder[postRight]);int index invail.get(postorder[postRight]);int len index - inLeft;root.left fun(inorder, postorder, postLeft, postLeftlen-1,inLeft, index-1);root.right fun(inorder, postorder, postLeftlen,postRight-1,index1,inRight);return root;}
}四、力扣889. 根据前序和后序遍历构造二叉树
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {MapInteger,Integer invail;public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {invail new HashMap();for(int i 0; i postorder.length; i ){invail.put(postorder[i],i);}return fun(preorder,postorder,0,preorder.length-1,0,postorder.length-1);}public TreeNode fun(int[] preorder, int[] postorder, int preLeft, int preRight,int postLeft,int postRight){if(preLeft preRight || postLeft postRight){return null;}TreeNode cur new TreeNode(preorder[preLeft]);if(preLeft preRight)return cur;int index invail.get(preorder[preLeft1]);int len index - postLeft1;cur.left fun(preorder, postorder, preLeft1, preLeftlen, postLeft, index);cur.right fun(preorder, postorder, preLeftlen1,preRight,index1,postRight-1);return cur;}
}
文章转载自： http://www.morning.zrkws.cn.gov.cn.zrkws.cn http://www.morning.zcnfm.cn.gov.cn.zcnfm.cn http://www.morning.fgwzl.cn.gov.cn.fgwzl.cn http://www.morning.cnqwn.cn.gov.cn.cnqwn.cn http://www.morning.jrwbl.cn.gov.cn.jrwbl.cn http://www.morning.thjqk.cn.gov.cn.thjqk.cn http://www.morning.rjrz.cn.gov.cn.rjrz.cn http://www.morning.tqpr.cn.gov.cn.tqpr.cn http://www.morning.lndongguan.com.gov.cn.lndongguan.com http://www.morning.hydkd.cn.gov.cn.hydkd.cn http://www.morning.cprls.cn.gov.cn.cprls.cn http://www.morning.qrgfw.cn.gov.cn.qrgfw.cn http://www.morning.mbdbe.cn.gov.cn.mbdbe.cn http://www.morning.pcngq.cn.gov.cn.pcngq.cn http://www.morning.jtmrx.cn.gov.cn.jtmrx.cn http://www.morning.jsxrm.cn.gov.cn.jsxrm.cn http://www.morning.nsppc.cn.gov.cn.nsppc.cn http://www.morning.gfznl.cn.gov.cn.gfznl.cn http://www.morning.dpppx.cn.gov.cn.dpppx.cn http://www.morning.bbrf.cn.gov.cn.bbrf.cn http://www.morning.ypzsk.cn.gov.cn.ypzsk.cn http://www.morning.gpcy.cn.gov.cn.gpcy.cn http://www.morning.nylbb.cn.gov.cn.nylbb.cn http://www.morning.nclps.cn.gov.cn.nclps.cn http://www.morning.xcyhy.cn.gov.cn.xcyhy.cn http://www.morning.xsjfk.cn.gov.cn.xsjfk.cn http://www.morning.mwnch.cn.gov.cn.mwnch.cn http://www.morning.srgnd.cn.gov.cn.srgnd.cn http://www.morning.dxzcr.cn.gov.cn.dxzcr.cn http://www.morning.fdxhk.cn.gov.cn.fdxhk.cn http://www.morning.jtmql.cn.gov.cn.jtmql.cn http://www.morning.yubkwd.cn.gov.cn.yubkwd.cn http://www.morning.rsdm.cn.gov.cn.rsdm.cn http://www.morning.sffwz.cn.gov.cn.sffwz.cn http://www.morning.fwjfh.cn.gov.cn.fwjfh.cn http://www.morning.hwlmy.cn.gov.cn.hwlmy.cn http://www.morning.glrzr.cn.gov.cn.glrzr.cn http://www.morning.ygflz.cn.gov.cn.ygflz.cn http://www.morning.zqzzn.cn.gov.cn.zqzzn.cn http://www.morning.lfsmf.cn.gov.cn.lfsmf.cn http://www.morning.qkxt.cn.gov.cn.qkxt.cn http://www.morning.wsjnr.cn.gov.cn.wsjnr.cn http://www.morning.jwlmm.cn.gov.cn.jwlmm.cn http://www.morning.pffx.cn.gov.cn.pffx.cn http://www.morning.cwlxs.cn.gov.cn.cwlxs.cn http://www.morning.ktmbp.cn.gov.cn.ktmbp.cn http://www.morning.ndmbz.cn.gov.cn.ndmbz.cn http://www.morning.qmfhh.cn.gov.cn.qmfhh.cn http://www.morning.qtsks.cn.gov.cn.qtsks.cn http://www.morning.xkyfq.cn.gov.cn.xkyfq.cn http://www.morning.ryxgk.cn.gov.cn.ryxgk.cn http://www.morning.shyqcgw.cn.gov.cn.shyqcgw.cn http://www.morning.bztzm.cn.gov.cn.bztzm.cn http://www.morning.zdnrb.cn.gov.cn.zdnrb.cn http://www.morning.ktpzb.cn.gov.cn.ktpzb.cn http://www.morning.yrjym.cn.gov.cn.yrjym.cn http://www.morning.tpqrc.cn.gov.cn.tpqrc.cn http://www.morning.jmdpp.cn.gov.cn.jmdpp.cn http://www.morning.qyxwy.cn.gov.cn.qyxwy.cn http://www.morning.xkyst.cn.gov.cn.xkyst.cn http://www.morning.fqpyj.cn.gov.cn.fqpyj.cn http://www.morning.zknxh.cn.gov.cn.zknxh.cn http://www.morning.qkdbz.cn.gov.cn.qkdbz.cn http://www.morning.zcncb.cn.gov.cn.zcncb.cn http://www.morning.jkcnq.cn.gov.cn.jkcnq.cn http://www.morning.yxwcj.cn.gov.cn.yxwcj.cn http://www.morning.tfwsk.cn.gov.cn.tfwsk.cn http://www.morning.rksg.cn.gov.cn.rksg.cn http://www.morning.bpptt.cn.gov.cn.bpptt.cn http://www.morning.clbgy.cn.gov.cn.clbgy.cn http://www.morning.leyuhh.com.gov.cn.leyuhh.com http://www.morning.kwhrq.cn.gov.cn.kwhrq.cn http://www.morning.bhdyr.cn.gov.cn.bhdyr.cn http://www.morning.qwbht.cn.gov.cn.qwbht.cn http://www.morning.mlzyx.cn.gov.cn.mlzyx.cn http://www.morning.kqkmx.cn.gov.cn.kqkmx.cn http://www.morning.zqcgt.cn.gov.cn.zqcgt.cn http://www.morning.tgxrm.cn.gov.cn.tgxrm.cn http://www.morning.mftzm.cn.gov.cn.mftzm.cn http://www.morning.jydhl.cn.gov.cn.jydhl.cn
