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

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

一、513.找树左下角的值

题目链接:https://leetcode.cn/problems/find-bottom-left-tree-value/
文章讲解: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
视频讲解:https://www.bilibili.com/video/BV1fA4y1o715

1.1 初见思路

  1. 层序遍历,最后一行的第一个元素就是要找的值
  2. 怎么知道到了最后一层:每层都更新一遍最左的元素值,没有再有下一层的时候就说明到最后一层了

1.2 具体实现

class Solution {int leftVal=0;public int findBottomLeftValue(TreeNode root) {Deque<TreeNode> queue = new LinkedList<>();queue.offer(root);int res = 0;while(!queue.isEmpty()){int size = queue.size();for(int i=0;i<size;i++){TreeNode node = queue.poll();if(i==0){res=node.val;}if(node.left!=null){queue.offer(node.left);}if(node.right!=null){queue.offer(node.right);}}}return res;}}

1.3 重难点

二、112. 路径总和

题目链接:https://leetcode.cn/problems/path-sum/
文章讲解:https://programmercarl.com/0112.%E8%B7%AF%E5%BE%84%E6%80%BB%E5%92%8C.html
视频讲解:https://www.bilibili.com/video/BV19t4y1L7CR

2.1 初见思路

  1. 递归+回溯
  2. 剪枝,当算出总和已经大于target了,这条分支的剩余计算都不用做了

2.2 具体实现

class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {if (root == null) {return false;}return hasSum(root, targetSum);}public boolean hasSum(TreeNode node, int target) {target -= node.val;if (node.left == null && node.right == null) {if (target == 0) {return true;}return false;}if (node.left != null) {boolean leftFlag = hasSum(node.left, target);if (leftFlag) {return true;}}if (node.right != null) {boolean rightFlag = hasSum(node.right, target);if (rightFlag) {return true;}}return false;}
}

2.3 重难点

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

题目链接:https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
文章讲解: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
视频讲解:https://www.bilibili.com/video/BV1vW4y1i7dn

3.1 初见思路

  1. 中序:左中右,后续:左右中
  2. 先用后序遍历找到根节点,再去中序中进行分割

3.2 具体实现

class Solution {HashMap<Integer,Integer> inorderArrayMap = new HashMap<>();int[] post;public TreeNode buildTree(int[] inorder, int[] postorder) {for(int i = 0;i < inorder.length; i++) {inorderArrayMap.put(inorder[i], i);//妙啊!将节点值及索引全部记录在哈希表中}post = postorder;TreeNode root = buildTree(0, inorder.length - 1, 0, post.length - 1);return root;}public TreeNode buildTree(int inorderStart, int inorderEnd, int postorderStart, int postorderEnd) {if(inorderEnd < inorderStart || postorderEnd < postorderStart) return null;int root = post[postorderEnd];//根据后序遍历结果,取得根节点int rootIndexInInorderArray = inorderArrayMap.get(root);//获取对应的索引TreeNode node = new TreeNode(root);//创建该节点node.left = buildTree(inorderStart, rootIndexInInorderArray - 1, postorderStart, postorderStart + rootIndexInInorderArray - inorderStart - 1);node.right = buildTree(rootIndexInInorderArray + 1, inorderEnd, postorderStart + rootIndexInInorderArray - inorderStart, postorderEnd - 1);return node;//注意!返回的是新建的node!}
}

3.3 重难点

  • 思路不难,实现有难度
  • 把中序遍历的值和下标存储在map中;这样能在后序遍历找到中节点后快速找到对应的在中序遍历中的下标

在这里插入图片描述

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



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

相关文章

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"