Day18:LeedCode 513.找树左下角的值 112. 路径总和 106.从中序与后序遍历序列构造二叉树

本文主要是介绍Day18:LeedCode 513.找树左下角的值 112. 路径总和 106.从中序与后序遍历序列构造二叉树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

513. 找树左下角的值

给定一个二叉树的 根节点 root,请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

示例 1:

 

294aeaf8d4977d45482b128bbf718283.jpeg

输入: root = [2,1,3]
输出: 1

 思路:出该二叉树的 最底层 最左边 节点的值=找出深度最大第一个结点(左结点先遍历)

方法一:递归法

如何找出深度最大的结点:回溯法,设置两个全局遍历maxlen,result记录最长深度,结果

图解:

120171f6743f49e0b5505720e41921fa.png

递归三部曲:

1.确定返回值和参数的类型

用一个全局变量记录最长深度,result记录结果,递归函数无返回值,参数为int len(当前深度),和传入结点TreeNode cur;

2.确认终止条件:

我们采用左优先遍历 ,遇到叶节点则return,如果该叶节点是深度更大的结点,则更新result;

3.单层递归逻辑:

用回溯法计算每个结点的深度

代码参考:

class Solution {int maxlen=-1;int result=0;public int findBottomLeftValue(TreeNode root) {//本题结点个数至少为1个travelsal(root,1);return result;}void travelsal(TreeNode cur,int len){//   if(root==null)return;if(cur.left==null&&cur.right==null){if(len>maxlen){//找到第一个深度更大的结点则更新resultresult=cur.val;maxlen=len;}return;}if(cur.left!=null){travelsal(cur.left,len+1);}//回溯,下一结点深度+1//本节点深度不变if(cur.right!=null){travelsal(cur.right,len+1);}//回溯,下一结点深度+1}
}

方法二:迭代法,层序遍历找到最后一排的第一个结点

层序遍历模板:

Day15:二叉树层序遍历 LeedCode 102.二叉树的层序遍历 199二叉树的右视图 637.二叉树的层平均值 101.对称二叉树 226.翻转二叉树-CSDN博客

代码参考:

class Solution {int result=0;public int findBottomLeftValue(TreeNode root) {Queue<TreeNode> myQ=new LinkedList<>();TreeNode cur=root;myQ.offer(cur);while(!myQ.isEmpty()){int len=myQ.size();for(int i=0;i<len;i++){//每层的第一个元素用来更新resultTreeNode temp=myQ.poll();if(i==0)result=temp.val;if(temp.left!=null){myQ.offer(temp.left);}if(temp.right!=null){myQ.offer(temp.right);}}}return result;}
}

112. 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ;否则,返回 false 。

叶子节点 是指没有子节点的节点。

示例 1:

 

6d411da702ef84d2a39823f28cda4f43.jpeg

输入:root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出:true
解释:等于目标和的根节点到叶节点路径如上图所示。

78c92f555024492faa375b7a807ec303.png

思路:用回溯法遍历所有路径

递归三部曲:

1.确定返回值和参数类型

返回一个boolean类型,参数为int sums(用targetSum依次减去路径上的值)和TreeNode cur(记录当前遍历到哪个结点)

因为targetSum不是全局变量,我们不能用sums==targetSum来判断是否找到路径,用targetSum依次减去路径上的值,sums==0代表找到

2.确定终止条件

遇到叶子结点判断sums是否等于0

 if(cur.left==null&&cur.right==null&&sums==0){return true;}
 if(cur.left==null&&cur.right==null)return false;

3.确定单层递归逻辑:

找到了就立即返回false,没找到就找其他路径,当所有路径都遍历完时,返回false

 if(cur.left!=null){
            if(travelsal(cur.left,sums-cur.left.val))return true;
        }
if(cur.right!=null){
            if(travelsal(cur.right,sums-cur.right.val))return true;
        }

class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {if(root==null)return false;return travelsal(root,targetSum-root.val);}boolean travelsal(TreeNode cur,int sums){if(cur.left==null&&cur.right==null&&sums==0){return true;}if(cur.left==null&&cur.right==null)return false;if(cur.left!=null){if(travelsal(cur.left,sums-cur.left.val))return true;}if(cur.right!=null){if(travelsal(cur.right,sums-cur.right.val))return true;}//遍历完所有路径均没找到,返回falsereturn false;}
}

方法二:迭代法

用栈来模拟回溯的过程:

1ebd3e6f285e4702bacc6d72124fef9d.png

思路:用一个栈放入所有分支路径,一个栈放入这些路径的总和值

class Solution {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.empty()){TreeNode cur=stack1.pop();Integer curSum=stack2.pop();//如果该节点为叶节点,且路径值==target 返回true;if(cur.left==null&&cur.right==null&&curSum==targetSum)return true;if(cur.left!=null){stack1.push(cur.left);stack2.push(curSum+cur.left.val);}if(cur.right!=null){stack1.push(cur.right);stack2.push(curSum+cur.right.val);}}return false;}
}

106. 从中序与后序遍历序列构造二叉树

给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。

示例 1:

 

42699c3c8a4d858737d7b228e5185049.jpeg

输入:inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出:[3,9,20,null,null,15,7]

4ae7bc1127244856b6fbf1975c737e5f.png

 思路:

  • 第一步:如果数组大小为零的话,说明是空节点了。

  • 第二步:如果不为空,那么取后序数组最后一个元素作为节点元素。

  • 第三步:找到后序数组最后一个元素在中序数组的位置,作为切割点

  • 第四步:切割中序数组,切成中序左数组和中序右数组 (顺序别搞反了,一定是先切中序数组)

  • 第五步:切割后序数组,切成后序左数组和后序右数组

  • 第六步:递归处理左区间和右区间

图解:

a2d59669b3f14e60bb2ee4bee3af1c76.png

 

代码:

class Solution {public TreeNode buildTree(int[] inorder, int[] postorder) {if(inorder.length==0)return null;//根据后序遍历找到根节点int rootValue=postorder[postorder.length-1];TreeNode root=new TreeNode(rootValue);//在中序遍历中找到根节点的位置int index=0;for(int i=0;i<inorder.length;i++){if(inorder[i]==rootValue) index=i;}//切割中序数组,中序数组在rootValue左边的值是左子树,在rootValue右边的值是右子树int[] left_inorder=Arrays.copyOfRange(inorder,0,index);int[] right_inorder=Arrays.copyOfRange(inorder,index+1,inorder.length);//切割后序数组int[] left_postorder=Arrays.copyOfRange(postorder,0,index);int[] right_postorder=Arrays.copyOfRange(postorder,index,postorder.length-1);root.left=buildTree(left_inorder,left_postorder);root.right=buildTree(right_inorder,right_postorder);return root;}
}

 注意:Arrays.copyOfRange()主要用于对一个已有的数组进行截取复制,复制出一个左闭右开区间的数组。

相似题目:

105. 从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。

 

示例 1:

 

042faf54261265f6eea664bcae95c621.jpeg

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

4ce108db8017420380cf1a05d4ef0e6a.png

代码:

class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {if(inorder.length==0)return null;//根据先序遍历找到根节点int rootValue=preorder[0];TreeNode root=new TreeNode(rootValue);//在中序遍历中找到根节点的位置int index=0;for(int i=0;i<inorder.length;i++){if(inorder[i]==rootValue) index=i;}//切割中序数组,中序数组在rootValue左边的值是左子树,在rootValue右边的值是右子树int[] left_inorder=Arrays.copyOfRange(inorder,0,index);int[] right_inorder=Arrays.copyOfRange(inorder,index+1,inorder.length);//切割先序序数组int[] left_preorder=Arrays.copyOfRange(preorder,1,1+index);int[] right_preorder=Arrays.copyOfRange(preorder,index+1,preorder.length);root.left=buildTree(left_preorder,left_inorder);root.right=buildTree(right_preorder,right_inorder);return root;}
}

 

 

 

 

 

这篇关于Day18:LeedCode 513.找树左下角的值 112. 路径总和 106.从中序与后序遍历序列构造二叉树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Linux修改pip和conda缓存路径的几种方法

《Linux修改pip和conda缓存路径的几种方法》在Python生态中,pip和conda是两种常见的软件包管理工具,它们在安装、更新和卸载软件包时都会使用缓存来提高效率,适当地修改它们的缓存路径... 目录一、pip 和 conda 的缓存机制1. pip 的缓存机制默认缓存路径2. conda 的缓

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》:本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK,或者在别人的电脑上,想

Python中Windows和macOS文件路径格式不一致的解决方法

《Python中Windows和macOS文件路径格式不一致的解决方法》在Python中,Windows和macOS的文件路径字符串格式不一致主要体现在路径分隔符上,这种差异可能导致跨平台代码在处理文... 目录方法 1:使用 os.path 模块方法 2:使用 pathlib 模块(推荐)方法 3:统一使

一文教你解决Python不支持中文路径的问题

《一文教你解决Python不支持中文路径的问题》Python是一种广泛使用的高级编程语言,然而在处理包含中文字符的文件路径时,Python有时会表现出一些不友好的行为,下面小编就来为大家介绍一下具体的... 目录问题背景解决方案1. 设置正确的文件编码2. 使用pathlib模块3. 转换路径为Unicod

MySQL9.0默认路径安装下重置root密码

《MySQL9.0默认路径安装下重置root密码》本文主要介绍了MySQL9.0默认路径安装下重置root密码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录问题描述环境描述解决方法正常模式下修改密码报错原因问题描述mysqlChina编程采用默认安装路径,

最长公共子序列问题的深度分析与Java实现方式

《最长公共子序列问题的深度分析与Java实现方式》本文详细介绍了最长公共子序列(LCS)问题,包括其概念、暴力解法、动态规划解法,并提供了Java代码实现,暴力解法虽然简单,但在大数据处理中效率较低,... 目录最长公共子序列问题概述问题理解与示例分析暴力解法思路与示例代码动态规划解法DP 表的构建与意义动

关于最长递增子序列问题概述

《关于最长递增子序列问题概述》本文详细介绍了最长递增子序列问题的定义及两种优化解法:贪心+二分查找和动态规划+状态压缩,贪心+二分查找时间复杂度为O(nlogn),通过维护一个有序的“尾巴”数组来高效... 一、最长递增子序列问题概述1. 问题定义给定一个整数序列,例如 nums = [10, 9, 2

C++中使用vector存储并遍历数据的基本步骤

《C++中使用vector存储并遍历数据的基本步骤》C++标准模板库(STL)提供了多种容器类型,包括顺序容器、关联容器、无序关联容器和容器适配器,每种容器都有其特定的用途和特性,:本文主要介绍C... 目录(1)容器及简要描述‌php顺序容器‌‌关联容器‌‌无序关联容器‌(基于哈希表):‌容器适配器‌:(

python获取当前文件和目录路径的方法详解

《python获取当前文件和目录路径的方法详解》:本文主要介绍Python中获取当前文件路径和目录的方法,包括使用__file__关键字、os.path.abspath、os.path.realp... 目录1、获取当前文件路径2、获取当前文件所在目录3、os.path.abspath和os.path.re