做视频网站的技能,成都的教育品牌网站建设,同创企业网站建设,怎么自己注册网站文章目录 1028. 从先序遍历还原二叉树#xff08;三种方法#xff1a;栈递归集合#xff09;一、栈 while迭代1.思路2.代码 二、递归法1.思路2.代码 三、集合存储1.思路2.代码 1028. 从先序遍历还原二叉树#xff08;三种方法#xff1a;栈递归集合#xff09; 一、栈 wh… 文章目录 1028. 从先序遍历还原二叉树三种方法栈递归集合一、栈 while迭代1.思路2.代码 二、递归法1.思路2.代码 三、集合存储1.思路2.代码 1028. 从先序遍历还原二叉树三种方法栈递归集合 一、栈 while迭代
1.思路
1.遍历整个字符串从0开始根节点在第0层 2.用level记录层数每遇到一个-字符当前层数1 3.用val记录要插入的结点的值遍历取到的数字通过字符运算得到值。 4.找到当前要插入结点的父结点栈的大小要小于当前层数 5.如果节点只有一个子节点那么保证该子节点为左子节点。 6.将创建的新结点入栈 7.除了根节点其他子节点全部出栈返回根节点
2.代码 public TreeNode recoverFromPreorder(String traversal) {StackTreeNode stack new Stack();//用栈来存储结点for (int i 0; i traversal.length(); ) {//遍历整个字符串从0开始根节点在第0层int level 0;//记录当前层数while (traversal.charAt(i) -) {//每遍历到一个-层数累加level;i;}int val 0;//查看当前要插入结点的数字while (i traversal.length() traversal.charAt(i) ! -) {//当前的字符是数字并且未超过字符串val val * 10 (traversal.charAt(i) - 0);//根据字符的相加遍历字符串找数字时 只能一个数字一个数字的转// 但是字符串中连续的数字是一个多位数需要前面的数字*10变高位再加上后面的数// 成为一个数作为新结点的值i;}while (stack.size() level) {stack.pop();//找到当前要插入结点的父结点}TreeNode node new TreeNode(val);//创建新结点if (!stack.isEmpty()) {//如果节点只有一个子节点那么保证该子节点为左子节点。if (stack.peek().left null) {stack.peek().left node;} else {stack.peek().right node;}}stack.add(node);//入栈}while (stack.size() 1) {stack.pop();//要返回根节点出到栈只有一个结点}return stack.pop();}二、递归法
1.思路
1.利用helper函数根据字符和对应深度创建结点还原二叉树 2.每遇到-字符层数加一 3.如果遍历的深度和获取到的深度不一致返回空 4.当深度等于层数时下一个结点的位置从index level开始 5.通过字符运算获取数字同时创建结点 6.根节点的左树调用helper函数递归如果左子节点是空那么右子节点肯定也是空的 7.如果根节点的左树不为空要想添加结点递归右树。 8.最终返回根节点
2.代码 //102. 二叉树的层序遍历---递归写法int index 0;//index记录遍历到字符串的哪个位置public TreeNode recoverFromPreorder3(String traversal) {return helper(traversal,0);}public TreeNode helper(String s, int depth) {//helper函数用来创建二叉树int level 0;//记录层数while (index level s.length() s.charAt(index level) -) {level;}//如果遍历的深度和获取到的深度不一致返回空if (level ! depth){return null;}int next index level;//获取数字while (next s.length() s.charAt(next) ! -)next;int val Integer.parseInt(s.substring(index level, next));index next;//创建结点TreeNode root new TreeNode(val);root.left helper(s, depth 1);if (root.left null) {//如果左子节点是空那么右子节点肯定也是空的root.right null;} else {root.right helper(s, depth 1);}return root;}三、集合存储
1.思路
1.使用正则匹配把字符串S拆成不同的数字存进数组中用集合list来存储结点 2.将根节点添加到list中层数从1开始不包括根节点 3.数组存储的位置不为空时根据转换的值创建结点 4.将结点加入到集合中 5.获取父结点插入结点并从新设置层数果满了层数加一 6.最终返回根节点
2.代码 //102. 二叉树的层序遍历--正则匹配public TreeNode recoverFromPreorder2(String traversal) {String[] valus traversal.split(-);//使用正则匹配把字符串S拆成不同的数字用集合list来存储结点ListTreeNode list new ArrayList();list.add(new TreeNode(Integer.valueOf(valus[0])));//根节点//根节点添加到list中int level 1;//层数层1开始不包括根节点for (int i 1; i valus.length; i) {if (!valus[i].isEmpty()) {//数组存储的位置不为空TreeNode node new TreeNode(Integer.valueOf(valus[i]));//根据转化的值创建结点//因为是前序遍历每层我们只需要存储一个结点即可这个节点值有可能//会被覆盖如果被覆盖了说明这个节点以及他的子节点都以及遍历过了//所以不用考虑被覆盖问题list.add(level, node);//将结点加入到集合中TreeNode parent list.get(level - 1);//获取父结点插入结点并从新设置层数if (parent.left null) {parent.left node;} else {parent.right node;}level 1;} else {level;//如果满了层数加一}}return list.get(0);}点击移步博客主页欢迎光临~
