代码随想录-算法训练营day18【二叉树05:找树左下角的值、路径总和、从中序与后序遍历序列构造二叉树】

本文主要是介绍代码随想录-算法训练营day18【二叉树05:找树左下角的值、路径总和、从中序与后序遍历序列构造二叉树】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

代码随想录-035期-算法训练营【博客笔记汇总表】-CSDN博客

第六章 二叉树 part05今日内容 ● 513.找树左下角的值
● 112. 路径总和  113.路径总和ii
● 106.从中序与后序遍历序列构造二叉树 105.从前序与中序遍历序列构造二叉树详细布置 找树左下角的值  本地递归偏难,反而迭代简单属于模板题, 两种方法掌握一下 题目链接/文章讲解/视频讲解:https://programmercarl.com/0513.%E6%89%BE%E6%A0%91%E5%B7%A6%E4%B8%8B%E8%A7%92%E7%9A%84%E5%80%BC.html  路径总和  本题 又一次设计要回溯的过程,而且回溯的过程隐藏的还挺深,建议先看视频来理解 112. 路径总和,和 113. 路径总和ii 一起做了。 优先掌握递归法。题目链接/文章讲解/视频讲解:https://programmercarl.com/0112.%E8%B7%AF%E5%BE%84%E6%80%BB%E5%92%8C.html  从中序与后序遍历序列构造二叉树 本题算是比较难的二叉树题目了,大家先看视频来理解。 106.从中序与后序遍历序列构造二叉树,105.从前序与中序遍历序列构造二叉树 一起做,思路一样的题目链接/文章讲解/视频讲解:https://programmercarl.com/0106.%E4%BB%8E%E4%B8%AD%E5%BA%8F%E4%B8%8E%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%E5%BA%8F%E5%88%97%E6%9E%84%E9%80%A0%E4%BA%8C%E5%8F%89%E6%A0%91.html 往日任务
● day 1 任务以及具体安排:https://docs.qq.com/doc/DUG9UR2ZUc3BjRUdY  
● day 2 任务以及具体安排:https://docs.qq.com/doc/DUGRwWXNOVEpyaVpG  
● day 3 任务以及具体安排:https://docs.qq.com/doc/DUGdqYWNYeGhlaVR6 
● day 4 任务以及具体安排:https://docs.qq.com/doc/DUFNjYUxYRHRVWklp 
● day 5 周日休息
● day 6 任务以及具体安排:https://docs.qq.com/doc/DUEtFSGdreWRuR2p4 
● day 7 任务以及具体安排:https://docs.qq.com/doc/DUElCb1NyTVpXa0Jj 
● day 8 任务以及具体安排:https://docs.qq.com/doc/DUGdsY2JFaFhDRVZH 
● day 9 任务以及具体安排:https://docs.qq.com/doc/DUHVXSnZNaXpVUHN4 
● day 10 任务以及具体安排:https://docs.qq.com/doc/DUElqeHh3cndDbW1Q 
●day 11 任务以及具体安排:https://docs.qq.com/doc/DUHh6UE5hUUZOZUd0 
●day 12 周日休息 
●day 13 任务以及具体安排:https://docs.qq.com/doc/DUHNpa3F4b2dMUWJ3 
●day 14 任务以及具体安排:https://docs.qq.com/doc/DUHRtdXZZSWFkeGdE 
●day 15 任务以及具体安排:https://docs.qq.com/doc/DUHN0ZVJuRmVYeWNv 
●day 16 任务以及具体安排:https://docs.qq.com/doc/DUHBQRm1aSWR4T2NK 
●day 17 任务以及具体安排:https://docs.qq.com/doc/DUFpXY3hBZkpabWFY

目录

0513_找树左下角的值

0112_路径总和

0113_路径总和ii

0106_从中序与后序遍历序列构造二叉树

0105_从前序与中序遍历序列构造二叉树


0513_找树左下角的值

package com.question.solve.leetcode.programmerCarl2._07_binaryTrees;import java.util.Deque;
import java.util.LinkedList;public class _0513_找树左下角的值 {
}/*** 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 Solution0513 {public int findBottomLeftValue(TreeNode root) {//迭代法int res = 0;if (root == null) {return res;}Deque<TreeNode> deuqe = new LinkedList<>();deuqe.offer(root);while (!deuqe.isEmpty()) {int size = deuqe.size();for (int i = 0; i < size; i++) {TreeNode poll = deuqe.poll();if (i == 0) {res = poll.val;}if (poll.left != null) {deuqe.offer(poll.left);}if (poll.right != null) {deuqe.offer(poll.right);}}}return res;}
}class Solution0513_2 {//递归法private int Deep = -1;private int value = 0;public int findBottomLeftValue(TreeNode root) {value = root.val;findLeftValue(root, 0);return value;}private void findLeftValue(TreeNode root, int deep) {if (root == null) return;if (root.left == null && root.right == null) {if (deep > Deep) {value = root.val;Deep = deep;}}if (root.left != null) findLeftValue(root.left, deep + 1);if (root.right != null) findLeftValue(root.right, deep + 1);}
}

0112_路径总和

package com.question.solve.leetcode.programmerCarl2._07_binaryTrees;import java.util.ArrayList;
import java.util.Stack;public class _0112_路径总和 {
}/*** 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 Solution0112 {public boolean hasPathSum(TreeNode root, int targetSum) {ArrayList<Integer> paths = new ArrayList<>();Boolean flag = false; //使用 Boolean包装类 来存储flag的状态traversal(root, paths, targetSum, flag);//flag不能是基本数据类型,return flag; //简化返回逻辑,直接返回flag//        int[] flag = new int[1]; //使用长度为1的数组来存储flag的状态
//        //Integer flag = 0; //使用 Integer包装类 来存储flag的状态
//        //Boolean flag = false; //使用 Boolean包装类 来存储flag的状态
//        traversal(root, paths, targetSum, flag);
//        return flag[0] == 1; //简化返回逻辑}private void traversal(TreeNode root, ArrayList<Integer> paths, int targetSum, Boolean flag) {if (root == null || flag) { //如果 flag 已经为 true,则不再进行遍历return;}paths.add(root.val);if (root.left == null && root.right == null) {int sum = 0;for (int x : paths) {sum += x;}if (sum == targetSum) {flag = true;return;}}if (root.left != null) {traversal(root.left, paths, targetSum, flag);paths.remove(paths.size() - 1);}if (root.right != null) {traversal(root.right, paths, targetSum, flag);paths.remove(paths.size() - 1);}}
}class Solution0112_2 {public boolean haspathsum(TreeNode root, int targetsum) {if (root == null) {return false;}targetsum -= root.val;//叶子结点if (root.left == null && root.right == null) {return targetsum == 0;}if (root.left != null) {boolean left = haspathsum(root.left, targetsum);if (left) {      //已经找到return true;}}if (root.right != null) {boolean right = haspathsum(root.right, targetsum);if (right) {     //已经找到return true;}}return false;}public boolean haspathsum2(TreeNode root, int targetsum) {//lc112 简洁方法if (root == null) return false; //为空退出//叶子节点判断是否符合if (root.left == null && root.right == null) return root.val == targetsum;//求两侧分支的路径和return haspathsum2(root.left, targetsum - root.val) || haspathsum(root.right, targetsum - root.val);}
}class Solution0112_3 {public boolean hasPathSum(TreeNode root, int targetSum) {if (root == null) return false;Stack<TreeNode> stack1 = new Stack<>();Stack<Integer> stack2 = new Stack<>();stack1.push(root);stack2.push(root.val);while (!stack1.isEmpty()) {int size = stack1.size();for (int i = 0; i < size; i++) {TreeNode node = stack1.pop();int sum = stack2.pop();//如果该节点是叶子节点了,同时该节点的路径数值等于sum,那么就返回trueif (node.left == null && node.right == null && sum == targetSum) {return true;}//右节点,压进去一个节点的时候,将该节点的路径数值也记录下来if (node.right != null) {stack1.push(node.right);stack2.push(sum + node.right.val);}//左节点,压进去一个节点的时候,将该节点的路径数值也记录下来if (node.left != null) {stack1.push(node.left);stack2.push(sum + node.left.val);}}}return false;}public boolean hasPathSum2(TreeNode root, int targetSum) {Stack<TreeNode> treeNodeStack = new Stack<>();Stack<Integer> sumStack = new Stack<>();if (root == null)return false;treeNodeStack.add(root);sumStack.add(root.val);while (!treeNodeStack.isEmpty()) {TreeNode curr = treeNodeStack.peek();int tempsum = sumStack.pop();if (curr != null) {treeNodeStack.pop();treeNodeStack.add(curr);treeNodeStack.add(null);sumStack.add(tempsum);if (curr.right != null) {treeNodeStack.add(curr.right);sumStack.add(tempsum + curr.right.val);}if (curr.left != null) {treeNodeStack.add(curr.left);sumStack.add(tempsum + curr.left.val);}} else {treeNodeStack.pop();TreeNode temp = treeNodeStack.pop();if (temp.left == null && temp.right == null && tempsum == targetSum)return true;}}return false;}
}

0113_路径总和ii

package com.question.solve.leetcode.programmerCarl2._07_binaryTrees;import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;public class _0113_路径总和II {
}/*** 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 Solution0113 {public List<List<Integer>> pathSum(TreeNode root, int targetSum) {List<List<Integer>> res = new ArrayList<>();if (root == null) {//非空判断return res;}List<Integer> paths = new ArrayList<>();traversal(root, targetSum, res, paths);return res;}private void traversal(TreeNode root, int targetSum, List<List<Integer>> res, List<Integer> paths) {if (root == null) {return;}paths.add(root.val);if (root.left == null && root.right == null) {int sum = paths.stream().mapToInt(Integer::intValue).sum();if (targetSum == sum) {res.add(new ArrayList<>(paths));}}if (root.left != null) {traversal(root.left, targetSum, res, paths);paths.remove(paths.size() - 1);}if (root.right != null) {traversal(root.right, targetSum, res, paths);paths.remove(paths.size() - 1);}}
}class Solution0113_2 {public List<List<Integer>> pathsum(TreeNode root, int targetsum) {List<List<Integer>> res = new ArrayList<>();if (root == null) return res;//非空判断List<Integer> path = new LinkedList<>();preOrderDfs(root, targetsum, res, path);return res;}public void preOrderDfs(TreeNode root, int targetsum, List<List<Integer>> res, List<Integer> path) {path.add(root.val);if (root.left == null && root.right == null) {//遇到了叶子节点if (targetsum - root.val == 0) {//找到了和为targetSum的路径res.add(new ArrayList<>(path));}return;//如果和不为targetSum,返回}if (root.left != null) {preOrderDfs(root.left, targetsum - root.val, res, path);path.remove(path.size() - 1); //回溯}if (root.right != null) {preOrderDfs(root.right, targetsum - root.val, res, path);path.remove(path.size() - 1); //回溯}}
}class Solution0113_3 {List<List<Integer>> result;LinkedList<Integer> path;public List<List<Integer>> pathSum(TreeNode root, int targetSum) {result = new LinkedList<>();path = new LinkedList<>();travesal(root, targetSum);return result;}private void travesal(TreeNode root, int count) {if (root == null) return;path.offer(root.val);count -= root.val;if (root.left == null && root.right == null && count == 0) {result.add(new LinkedList<>(path));}travesal(root.left, count);travesal(root.right, count);path.removeLast();//回溯}
}class Solution0113_4 {public List<List<Integer>> pathSum(TreeNode root, int targetSum) {//DFS统一迭代法List<List<Integer>> result = new ArrayList<>();Stack<TreeNode> nodeStack = new Stack<>();Stack<Integer> sumStack = new Stack<>();Stack<ArrayList<Integer>> pathStack = new Stack<>();if (root == null)return result;nodeStack.add(root);sumStack.add(root.val);pathStack.add(new ArrayList<>());while (!nodeStack.isEmpty()) {TreeNode currNode = nodeStack.peek();int currSum = sumStack.pop();ArrayList<Integer> currPath = pathStack.pop();if (currNode != null) {nodeStack.pop();nodeStack.add(currNode);nodeStack.add(null);sumStack.add(currSum);currPath.add(currNode.val);pathStack.add(new ArrayList(currPath));if (currNode.right != null) {nodeStack.add(currNode.right);sumStack.add(currSum + currNode.right.val);pathStack.add(new ArrayList(currPath));}if (currNode.left != null) {nodeStack.add(currNode.left);sumStack.add(currSum + currNode.left.val);pathStack.add(new ArrayList(currPath));}} else {nodeStack.pop();TreeNode temp = nodeStack.pop();if (temp.left == null && temp.right == null && currSum == targetSum)result.add(new ArrayList(currPath));}}return result;}
}

0106_从中序与后序遍历序列构造二叉树

package com.question.solve.leetcode.programmerCarl2._07_binaryTrees;import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;public class _0106_从中序与后序遍历序列构造二叉树 {
}/*** 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 Solution0106 {Map<Integer, Integer> map; //方便根据数值查找位置public TreeNode buildTree(int[] inorder, int[] postorder) {map = new HashMap<>();for (int i = 0; i < inorder.length; i++) { //用map保存中序序列的数值对应位置map.put(inorder[i], i);}return findNode(inorder, 0, inorder.length, postorder, 0, postorder.length);  // 前闭后开}public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {//参数里的范围都是前闭后开if (inBegin >= inEnd || postBegin >= postEnd) {  // 不满足左闭右开,说明没有元素,返回空树return null;}int rootIndex = map.get(postorder[postEnd - 1]);  // 找到后序遍历的最后一个元素在中序遍历中的位置TreeNode root = new TreeNode(inorder[rootIndex]);  // 构造结点int lenOfLeft = rootIndex - inBegin;  // 保存中序左子树个数,用来确定后序数列的个数root.left = findNode(inorder, inBegin, rootIndex,postorder, postBegin, postBegin + lenOfLeft);root.right = findNode(inorder, rootIndex + 1, inEnd,postorder, postBegin + lenOfLeft, postEnd - 1);return root;}
}class Solution0106_2 {public TreeNode buildTree(int[] inorder, int[] postorder) {if (postorder.length == 0 || inorder.length == 0)return null;return buildHelper(inorder, 0, inorder.length, postorder, 0, postorder.length);}private TreeNode buildHelper(int[] inorder, int inorderStart, int inorderEnd, int[] postorder, int postorderStart, int postorderEnd) {if (postorderStart == postorderEnd)return null;int rootVal = postorder[postorderEnd - 1];TreeNode root = new TreeNode(rootVal);int middleIndex;for (middleIndex = inorderStart; middleIndex < inorderEnd; middleIndex++) {if (inorder[middleIndex] == rootVal)break;}int leftInorderStart = inorderStart;int leftInorderEnd = middleIndex;int rightInorderStart = middleIndex + 1;int rightInorderEnd = inorderEnd;int leftPostorderStart = postorderStart;int leftPostorderEnd = postorderStart + (middleIndex - inorderStart);int rightPostorderStart = leftPostorderEnd;int rightPostorderEnd = postorderEnd - 1;root.left = buildHelper(inorder, leftInorderStart, leftInorderEnd, postorder, leftPostorderStart, leftPostorderEnd);root.right = buildHelper(inorder, rightInorderStart, rightInorderEnd, postorder, rightPostorderStart, rightPostorderEnd);return root;}
}class Solution0106_3 {public TreeNode buildTree(int[] inorder, int[] postorder) {if (postorder == null || postorder.length == 0) {return null;}TreeNode root = new TreeNode(postorder[postorder.length - 1]);Deque<TreeNode> stack = new LinkedList<TreeNode>();stack.push(root);int inorderIndex = inorder.length - 1;for (int i = postorder.length - 2; i >= 0; i--) {int postorderVal = postorder[i];TreeNode node = stack.peek();if (node.val != inorder[inorderIndex]) {node.right = new TreeNode(postorderVal);stack.push(node.right);} else {while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {node = stack.pop();inorderIndex--;}node.left = new TreeNode(postorderVal);stack.push(node.left);}}return root;}
}

0105_从前序与中序遍历序列构造二叉树

package com.question.solve.leetcode.programmerCarl2._07_binaryTrees;import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;public class _0105_从前序与中序遍历序列构造二叉树 {
}/*** 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 Solution0105 {Map<Integer, Integer> map;public TreeNode buildTree(int[] preorder, int[] inorder) {map = new HashMap<>();for (int i = 0; i < inorder.length; i++) {//用map保存中序序列的数值对应位置map.put(inorder[i], i);}return findNode(preorder, 0, preorder.length, inorder, 0, inorder.length); //前闭后开}public TreeNode findNode(int[] preorder, int preBegin, int preEnd, int[] inorder, int inBegin, int inEnd) {//参数里的范围都是前闭后开if (preBegin >= preEnd || inBegin >= inEnd) {//不满足左闭右开,说明没有元素,返回空树return null;}int rootIndex = map.get(preorder[preBegin]);  //找到前序遍历的第一个元素在中序遍历中的位置TreeNode root = new TreeNode(inorder[rootIndex]);  //构造结点int lenOfLeft = rootIndex - inBegin;  //保存中序左子树个数,用来确定前序数列的个数root.left = findNode(preorder, preBegin + 1, preBegin + lenOfLeft + 1,inorder, inBegin, rootIndex);root.right = findNode(preorder, preBegin + lenOfLeft + 1, preEnd,inorder, rootIndex + 1, inEnd);return root;}
}class Solution0105_2 {public TreeNode buildTree(int[] preorder, int[] inorder) {if (preorder == null || preorder.length == 0) {return null;}TreeNode root = new TreeNode(preorder[0]);Deque<TreeNode> stack = new LinkedList<TreeNode>();stack.push(root);int inorderIndex = 0;for (int i = 1; i < preorder.length; i++) {int preorderVal = preorder[i];TreeNode node = stack.peek();if (node.val != inorder[inorderIndex]) {node.left = new TreeNode(preorderVal);stack.push(node.left);} else {while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {node = stack.pop();inorderIndex++;}node.right = new TreeNode(preorderVal);stack.push(node.right);}}return root;}
}

这篇关于代码随想录-算法训练营day18【二叉树05:找树左下角的值、路径总和、从中序与后序遍历序列构造二叉树】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/922248

相关文章

Java 接口定义变量的示例代码

《Java接口定义变量的示例代码》文章介绍了Java接口中的变量和方法,接口中的变量必须是publicstaticfinal的,用于定义常量,而方法默认是publicabstract的,必须由实现类... 在 Java 中,接口是一种抽象类型,用于定义类必须实现的方法。接口可以包含常量和方法,但不能包含实例

使用Redis实现会话管理的示例代码

《使用Redis实现会话管理的示例代码》文章介绍了如何使用Redis实现会话管理,包括会话的创建、读取、更新和删除操作,通过设置会话超时时间并重置,可以确保会话在用户持续活动期间不会过期,此外,展示了... 目录1. 会话管理的基本概念2. 使用Redis实现会话管理2.1 引入依赖2.2 会话管理基本操作

mybatis-plus分表实现案例(附示例代码)

《mybatis-plus分表实现案例(附示例代码)》MyBatis-Plus是一个MyBatis的增强工具,在MyBatis的基础上只做增强不做改变,为简化开发、提高效率而生,:本文主要介绍my... 目录文档说明数据库水平分表思路1. 为什么要水平分表2. 核心设计要点3.基于数据库水平分表注意事项示例

Nginx服务器部署详细代码实例

《Nginx服务器部署详细代码实例》Nginx是一个高性能的HTTP和反向代理web服务器,同时也提供了IMAP/POP3/SMTP服务,:本文主要介绍Nginx服务器部署的相关资料,文中通过代码... 目录Nginx 服务器SSL/TLS 配置动态脚本反向代理总结Nginx 服务器Nginx是一个‌高性

MybatisPlus中几种条件构造器运用方式

《MybatisPlus中几种条件构造器运用方式》QueryWrapper是Mybatis-Plus提供的一个用于构建SQL查询条件的工具类,提供了各种方法如eq、ne、gt、ge、lt、le、lik... 目录版本介绍QueryWrapperLambdaQueryWrapperUpdateWrapperL

HTML5的input标签的`type`属性值详解和代码示例

《HTML5的input标签的`type`属性值详解和代码示例》HTML5的`input`标签提供了多种`type`属性值,用于创建不同类型的输入控件,满足用户输入的多样化需求,从文本输入、密码输入、... 目录一、引言二、文本类输入类型2.1 text2.2 password2.3 textarea(严格

JAVA项目swing转javafx语法规则以及示例代码

《JAVA项目swing转javafx语法规则以及示例代码》:本文主要介绍JAVA项目swing转javafx语法规则以及示例代码的相关资料,文中详细讲解了主类继承、窗口创建、布局管理、控件替换、... 目录最常用的“一行换一行”速查表(直接全局替换)实际转换示例(JFramejs → JavaFX)迁移建

Go异常处理、泛型和文件操作实例代码

《Go异常处理、泛型和文件操作实例代码》Go语言的异常处理机制与传统的面向对象语言(如Java、C#)所使用的try-catch结构有所不同,它采用了自己独特的设计理念和方法,:本文主要介绍Go异... 目录一:异常处理常见的异常处理向上抛中断程序恢复程序二:泛型泛型函数泛型结构体泛型切片泛型 map三:文

MyBatis中的两种参数传递类型详解(示例代码)

《MyBatis中的两种参数传递类型详解(示例代码)》文章介绍了MyBatis中传递多个参数的两种方式,使用Map和使用@Param注解或封装POJO,Map方式适用于动态、不固定的参数,但可读性和安... 目录✅ android方式一:使用Map<String, Object>✅ 方式二:使用@Param

SpringBoot实现图形验证码的示例代码

《SpringBoot实现图形验证码的示例代码》验证码的实现方式有很多,可以由前端实现,也可以由后端进行实现,也有很多的插件和工具包可以使用,在这里,我们使用Hutool提供的小工具实现,本文介绍Sp... 目录项目创建前端代码实现约定前后端交互接口需求分析接口定义Hutool工具实现服务器端代码引入依赖获