题目考察的知识点 二叉树的遍历 题目解答方法的文字分析 本算法主要结构是，用dfs算法遍历整棵二叉树，找到最近公共祖先，然后返回它的值 dfs算法详解： 1、p和q在二叉树两侧，则找最近的root结点。 2、p和q在二叉树同侧，则找p或者q。 具体的判断为： (1)如果left和right均不为空，说明p和q一个在左子树一个在右子树，返回当前root节点； (2)如果left为空，right不为空，说明p和q都在右子树中，返回right； (3)如果left不为空，right为空，说明p和q都在左子树中，返回left。 本题解析所用的编程语言 java 完整且正确的...

题目考察的知识点 二叉树的遍历，深度优先搜索 题目解答方法的文字分析 利用二叉树的层次遍历方法遍历整棵二叉树，然后在节点出队的时候，判断节点的值是否在low和high之间，是的话就和ans相加。当遍历完二叉树后，ans的值即为答案。 本题解析所用的编程语言 java 完整且正确的编程代码 import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNo...

题目考察的知识点 二叉树的遍历 题目解答方法的文字分析 首先通过广度优先搜索遍历二叉树，在遍历的过程中，将所有的节点值都放入队列list中。再通过遍历队列，将值存到数组中，最后用java自带的方法将数组按从小到大排列，所得即为答案 本题解析所用的编程语言 java 完整且正确的编程代码 import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNod...

题目考察的知识点 二叉树的遍历 题目解答方法的文字分析 进行二叉树的层次遍历，在遍历当前一层的时候，将下一层的节点入队，直到队列为空，整棵二叉树遍历完毕。当节点出队时，统计节点数量，直到队列为空就可以得到整棵二叉树的节点数量 本题解析所用的编程语言 java 完整且正确的编程代码 import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(i...

题目考察的知识点 二叉树的遍历 题目解答方法的文字分析 对于二叉树中的一个节点，该节点的最大路径和取决于该节点的值与该节点的左右子节点的单向的最大路径和，如果子节点单向的最大路径和为正，则计入该节点的最大路径和，否则不计入该节点的最大路径和。维护一个全局变量 maxSum 存储最大路径和，在递归过程中更新 maxSum 的值，最后得到的 maxSum 的值即为二叉树中的最大路径和。 本题解析所用的编程语言 java 完整且正确的编程代码 import java.util.*; /* * public class TreeNode { * int val = ...

题目考察的知识点 二叉树的遍历，深度优先搜索 题目解答方法的文字分析 从根节点开始，遍历每个节点，如果遇到叶子节点，则将叶子节点对应的数字加到数字之和。如果当前节点不是叶子节点，则计算其子节点对应的数字，并将字节点相加，然后对子节点递归遍历。 本题解析所用的编程语言 java 完整且正确的编程代码 import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public T...

题目考察的知识点 二叉树的中序遍历 题目解答方法的文字分析 这道题的本质就是将二叉树的叶子节点值从左到右保存到数组下。符合从左到右的遍历顺序就是中序遍历。直接中序遍历二叉树，遍历到叶子节点就将值保存到队列当中，由于队列先进先出的特点，可以有效保存值的顺序。 本题解析所用的编程语言 java 完整且正确的编程代码 import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * p...

题目考察的知识点 二叉树的层次遍历 题目解答方法的文字分析 本题的本质是求二叉树每一层的第一个节点的值。所以使用二叉树的层次遍历即可求出答案。由于我们在遍历每一层时，都会记录队列的长度size,所以我们只要在二叉树遍历每一层时，比较size和每层的节点数目-1（size在进入循环之后，减去了一）是否相同即可，若相同，代表是第一个值，加入队列list即可。最后将队列转换为数组即为答案。 本题解析所用的编程语言 java 完整且正确的编程代码 import java.util.*; /* * public class TreeNode { * int val =...

题目考察的知识点 二叉树的遍历，层次遍历 题目解答方法的文字分析 通过层次遍历以及在层次遍历时先统计本层的TreeNode个数size，然后在每一层的遍历过程中，统计每一层的和sum,然后用队列list装载每一层的平均重量sum/size。因为队列具有先进先出的特点，能够保证层的顺序。最后将平局重量装入double[]即可。 本题解析所用的编程语言 java 完整且正确的编程代码 import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null;...

题目考察的知识点 二叉树的遍历，层次遍历 题目解答方法的文字分析 首先通过二叉树的层次遍历，将二叉树所有的节点值保存到list中，然后将list转化成数组，再将数组从小到大排序。因为最小体重差必定是在排序后的数组res中的两个相邻的体重之间产生，所以从0到list.length-1顺序遍历，将ans和res[i+1]-res[i]比较，其中，i代表当前值。将较小值赋给ans,遍历完毕后即可得到答案。 本题解析所用的编程语言 java 完整且正确的编程代码 import java.util.*; /* * public class TreeNode { * i...

题目考察的知识点 二叉树的遍历，深度优先搜索，递归 题目解答方法的文字分析 这道题的本质就是遍历所有所有根节点到叶子节点的路径，找出符合targetsum等于根节点到叶子节点的路径上所有节点值的和，换个思考角度，我们每遍历一层就将targetsum-root.val的值传递下去，直到传到某一个叶子节点符合targetsum-root.val=0；则可返回true,否则返回false。因为根节点将targetsum-root.val传给左右子树，而其左右子树继续同样的操作，为此我们可以使用递归来完成这些操作。 本题解析所用的编程语言 java 完整且正确的编程代码 im...

题目考察的知识点 二叉树的遍历，层次遍历 题目解答方法的文字分析 本题可以用二叉树的广度优先搜索来解决。因为二叉树的层数就是二叉树的最大深度。而牛群的最短路径就是看二叉树哪一层先出现叶子节点。遍历每一层时，搜索叶子节点，当搜索到时，返回层数，层数便是最短路径长度。 本题解析所用的编程语言 java 完整且正确的编程代码 import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; *...

题目考察的知识点 二叉树的深度优先搜索和广度优先搜索 题目解答方法的文字分析 二叉树从上到下的每一层的深度，等于他的左子树和右子树中最大深度+这一层的深度1。即如果我们知道了左子树和右子树的最大深度 l 和 r，那么该二叉树的最大深度即为： max⁡(l,r)+1 而左子树和右子树的最大深度又可以以同样的方式进行计算。因此我们可以用深度优先搜索的方法，递归计算二叉树的最大深度。 本题解析所用的编程语言 java 完整且正确的编程代码 import java.util.*; /* * public class TreeNode { * int val = ...

题目考察的知识点 二叉搜索树的性质以及中序遍历的理解 题目解答方法的文字分析 由NB25题我们可以知道，二叉搜索树的中序遍历是递增的，因为我们逆中序遍历是递减的，即先右子树，再遍历中间节点，然后遍历左子树，得到的便是递减序列，遍历到第k个值，便是第k大的值。 为求第 k个节点，需要实现以下 三项工作 ： 递归遍历时计数，统计当前节点的序号； 递归到第 k个节点时，应记录结果 resresres ； 记录结果后，后续的遍历即失去意义，应提前终止（即返回）。 本题解析所用的编程语言 java 完整且正确的编程代码 import java.util.*; /* * pu...