【每日力扣】437. 路径总和 III 与105. 从前序与中序遍历序列构造二叉树

本文主要是介绍【每日力扣】437. 路径总和 III 与105. 从前序与中序遍历序列构造二叉树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

在这里插入图片描述

🔥 个人主页: 黑洞晓威
😀你不必等到非常厉害,才敢开始,你需要开始,才会变的非常厉害

437. 路径总和 III

给定一个二叉树的根节点 root ,和一个整数 targetSum ,求该二叉树里节点值之和等于 targetSum路径 的数目。

路径 不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。

解题思路

  1. 由于路径不必从根节点开始,也不必在叶子节点结束,所以对于每个节点,都要尝试以该节点作为路径的起点,向下搜索满足条件的路径数量。
  2. 递归遍历节点,并分别计算包含当前节点以及不包含当前节点的路径数。
  3. 对于每个节点,递归计算包含当前节点的路径数量,然后递归计算不包含当前节点的路径数量。
  4. 统计符合条件的路径数量。

代码实现

class Solution {public int pathSum(TreeNode root, int targetSum) {if (root == null) {return 0;}// 以当前节点为路径起点的路径数 + 以左子树为路径起点的路径数 + 以右子树为路径起点的路径数int pathsFromRoot = countPaths(root, targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);return pathsFromRoot;}private int countPaths(TreeNode node, int targetSum) {if (node == null) {return 0;}int count = 0;if (node.val == targetSum) {count++;}count += countPaths(node.left, targetSum - node.val);count += countPaths(node.right, targetSum - node.val);return count;}
}

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

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

解题思路

  1. 先序遍历的第一个元素为当前树的根节点。
  2. 在中序遍历中找到根节点的位置,左边为左子树的中序遍历,右边为右子树的中序遍历。
  3. 递归构建左子树和右子树。

代码实现

class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {return buildTreeHelper(preorder, inorder, 0, 0, inorder.length - 1);}private TreeNode buildTreeHelper(int[] preorder, int[] inorder, int preStart, int inStart, int inEnd) {if (preStart > preorder.length - 1 || inStart > inEnd) {return null;}TreeNode root = new TreeNode(preorder[preStart]);int inIndex = 0;for (int i = inStart; i <= inEnd; i++) {if (inorder[i] == root.val) {inIndex = i;}}root.left = buildTreeHelper(preorder, inorder, preStart + 1, inStart, inIndex - 1);root.right = buildTreeHelper(preorder, inorder, preStart + inIndex - inStart + 1, inIndex + 1, inEnd);return root;}
}

这篇关于【每日力扣】437. 路径总和 III 与105. 从前序与中序遍历序列构造二叉树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

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

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

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

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数

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

图的实现方式 邻接矩阵法 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