代码随想录-算法训练营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

相关文章

python获取指定名字的程序的文件路径的两种方法

《python获取指定名字的程序的文件路径的两种方法》本文主要介绍了python获取指定名字的程序的文件路径的两种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要... 最近在做项目,需要用到给定一个程序名字就可以自动获取到这个程序在Windows系统下的绝对路径,以下

SpringBoot路径映射配置的实现步骤

《SpringBoot路径映射配置的实现步骤》本文介绍了如何在SpringBoot项目中配置路径映射,使得除static目录外的资源可被访问,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一... 目录SpringBoot路径映射补:springboot 配置虚拟路径映射 @RequestMapp

Redis实现高效内存管理的示例代码

《Redis实现高效内存管理的示例代码》Redis内存管理是其核心功能之一,为了高效地利用内存,Redis采用了多种技术和策略,如优化的数据结构、内存分配策略、内存回收、数据压缩等,下面就来详细的介绍... 目录1. 内存分配策略jemalloc 的使用2. 数据压缩和编码ziplist示例代码3. 优化的

C# LiteDB处理时间序列数据的高性能解决方案

《C#LiteDB处理时间序列数据的高性能解决方案》LiteDB作为.NET生态下的轻量级嵌入式NoSQL数据库,一直是时间序列处理的优选方案,本文将为大家大家简单介绍一下LiteDB处理时间序列数... 目录为什么选择LiteDB处理时间序列数据第一章:LiteDB时间序列数据模型设计1.1 核心设计原则

Python 基于http.server模块实现简单http服务的代码举例

《Python基于http.server模块实现简单http服务的代码举例》Pythonhttp.server模块通过继承BaseHTTPRequestHandler处理HTTP请求,使用Threa... 目录测试环境代码实现相关介绍模块简介类及相关函数简介参考链接测试环境win11专业版python

Python从Word文档中提取图片并生成PPT的操作代码

《Python从Word文档中提取图片并生成PPT的操作代码》在日常办公场景中,我们经常需要从Word文档中提取图片,并将这些图片整理到PowerPoint幻灯片中,手动完成这一任务既耗时又容易出错,... 目录引言背景与需求解决方案概述代码解析代码核心逻辑说明总结引言在日常办公场景中,我们经常需要从 W

使用Spring Cache本地缓存示例代码

《使用SpringCache本地缓存示例代码》缓存是提高应用程序性能的重要手段,通过将频繁访问的数据存储在内存中,可以减少数据库访问次数,从而加速数据读取,:本文主要介绍使用SpringCac... 目录一、Spring Cache简介核心特点:二、基础配置1. 添加依赖2. 启用缓存3. 缓存配置方案方案

MySQL的配置文件详解及实例代码

《MySQL的配置文件详解及实例代码》MySQL的配置文件是服务器运行的重要组成部分,用于设置服务器操作的各种参数,下面:本文主要介绍MySQL配置文件的相关资料,文中通过代码介绍的非常详细,需要... 目录前言一、配置文件结构1.[mysqld]2.[client]3.[mysql]4.[mysqldum

Python多线程实现大文件快速下载的代码实现

《Python多线程实现大文件快速下载的代码实现》在互联网时代,文件下载是日常操作之一,尤其是大文件,然而,网络条件不稳定或带宽有限时,下载速度会变得很慢,本文将介绍如何使用Python实现多线程下载... 目录引言一、多线程下载原理二、python实现多线程下载代码说明:三、实战案例四、注意事项五、总结引

IDEA与MyEclipse代码量统计方式

《IDEA与MyEclipse代码量统计方式》文章介绍在项目中不安装第三方工具统计代码行数的方法,分别说明MyEclipse通过正则搜索(排除空行和注释)及IDEA使用Statistic插件或调整搜索... 目录项目场景MyEclipse代码量统计IDEA代码量统计总结项目场景在项目中,有时候我们需要统计