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

相关文章

hdu2544(单源最短路径)

模板题: //题意:求1到n的最短路径,模板题#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#i

poj 1734 (floyd求最小环并打印路径)

题意: 求图中的一个最小环,并打印路径。 解析: ans 保存最小环长度。 一直wa,最后终于找到原因,inf开太大爆掉了。。。 虽然0x3f3f3f3f用memset好用,但是还是有局限性。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#incl

uva 10131 最长子序列

题意: 给大象的体重和智商,求体重按从大到小,智商从高到低的最长子序列,并输出路径。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vect

POJ1631最长单调递增子序列

最长单调递增子序列 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.util.StringTokenizer;publ

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

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: 3/ \9 20/ \15 7   class Solution {public TreeNode buildTree(int[] pr

【408DS算法题】039进阶-判断图中路径是否存在

Index 题目分析实现总结 题目 对于给定的图G,设计函数实现判断G中是否含有从start结点到stop结点的路径。 分析实现 对于图的路径的存在性判断,有两种做法:(本文的实现均基于邻接矩阵存储方式的图) 1.图的BFS BFS的思路相对比较直观——从起始结点出发进行层次遍历,遍历过程中遇到结点i就表示存在路径start->i,故只需判断每个结点i是否就是stop

Android Environment 获取的路径问题

1. 以获取 /System 路径为例 /*** Return root of the "system" partition holding the core Android OS.* Always present and mounted read-only.*/public static @NonNull File getRootDirectory() {return DIR_ANDR

图的最短路径算法——《啊哈!算法》

图的实现方式 邻接矩阵法 int[][] map;// 图的邻接矩阵存储法map = new int[5][5];map[0] = new int[] {0, 1, 2, 3, 4};map[1] = new int[] {1, 0, 2, 6, 4};map[2] = new int[] {2, 999, 0, 3, 999};map[3] = new int[] {3, 7

PHP实现二叉树遍历(非递归方式,栈模拟实现)

二叉树定义是这样的:一棵非空的二叉树由根结点及左、右子树这三个基本部分组成,根据节点的访问位置不同有三种遍历方式: ① NLR:前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR:中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。 ③ LRN:后序遍历(PostorderT

vcpkg子包路径批量获取

获取vcpkg 子包的路径,并拼接为set(CMAKE_PREFIX_PATH “拼接路径” ) import osdef find_directories_with_subdirs(root_dir):# 构建根目录下的 "packages" 文件夹路径root_packages_dir = os.path.join(root_dir, "packages")# 如果 "packages"