觅杳 - 个人主页动态

2023-02-15 16:19

考虑层序遍历如果当前节点的左右子树任一为空，判断同层的下一个节点的左右子树是否都为空即可 import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请...

0 点赞评论收藏

2023-02-14 22:33

西安理工大学 Java

题解 | #判断是不是二叉搜索树#

二叉搜索树：中序遍历有序，只要判断每一个前一个元素是否都小于其后一个元素即可采用递归遇到空，返回true先遍历left，不符合返回false；针对root，如果前大于后，返回false；反之，更新pre，返回right结果 import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } *...

0 点赞评论收藏

2023-02-11 18:27

西安理工大学 Java

题解 | #数组中出现次数超过一半的数字#

使用摩尔选举，遇到与res一致的，就增加num；反之，减少num如果，num = 0，那么就更新res为当前的数组值。 public class Solution { public int MoreThanHalfNum_Solution(int[] array) { // 使用摩尔选举 int res = array[0], num = 0; for (int i = 0; i < array.length; ++i) { if (num == 0) { res = arra...

0 点赞评论收藏

2023-02-11 18:11

西安理工大学 Java

题解 | #有效括号序列#

使用栈，遇到右括号就出栈，遇到左括号就进栈。最后，判断栈是否为空，从而返回相应结果。以左括号为值，右括号为键进行存储到map中，方便判断遇到的是哪个括号，以及是该括号的左半部分还是右半部分。由此，确定左右括号的办法，就是与map中存储的值键进行比对。遇到右括号，且左括号与之匹配，则将左括号出栈；反之，返回false。 import java.util.*; public class Solution { /** * * @param s string字符串 * @return bool布尔型 */ public boolean i...

0 点赞评论收藏

2023-02-02 21:44

西安理工大学 Java

题解 | #合并二叉树#

// 同时遍历两棵树即可 // 递归返回值和参数：返回值就是TreeNode，参数是t1和t2 // 递归终结：如果都为null，返回null；一方为null，返回另一方 // 单层逻辑：合并结果，左侧为左子树合并结果，右侧为右子树合并结果 import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Solution { /** ...

0 点赞评论收藏

2023-01-27 16:16

西安理工大学 Java

题解 | #二叉搜索树的最近公共祖先#

通过画图分析可知，二叉树的最近公共祖先，其实就是第一个出现在p和q的返回之内的节点但是由于p和q的大小关系不确定，所以无法直接写出范围，所以，反向思维，写 root.val都大于或都小于，两者都不满足的话，就说明在二者的范围之内，那么直接返回即可 import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = va...

0 点赞评论收藏

2023-01-27 16:06

西安理工大学 Java

题解 | #二叉树的后序遍历#

import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param...

0 点赞评论收藏

2023-01-10 16:10

西安理工大学 Java

题解 | #判断是不是平衡二叉树#

平衡二叉树的定义：左右子树高度差的绝对值 <= 1，且左右子树都是平衡二叉树显然，具有递归特性，考虑使用递归。此时，需要计算左右子树的高度差，以及左右子树各自是否是平衡二叉树，显然一个是int，一个是boolean需要确定递归过程或者说递归返回值，是递归深度int，还是递归是否是平衡二叉树boolean，由于是否是平衡二叉树是结果，判断过程依赖于深度，且递归boolean不便于确定递归终止条件，所以主要递归深度。考虑将深度int转化为是否为平衡二叉树的boolean，可以 设非平衡二叉树的深度返回值为-1，平衡二叉树返回非-1的具体深度值 public class Solution { ...

0 点赞评论收藏

2023-01-09 17:46

西安理工大学 Java

题解 | #二叉树的最小深度#

考虑类似于最大深度的求法，即使用递归。到达叶子节点，即左右节点都为null，返回 0(较小的深度，但两边都是0) + 1；节点的左右子树都不为null，返回左右子树较小的深度 + 1；节点的左右子树只有一方为null时，求法有所不同，要返回的应该是左右子树深度较大的 + 1，而不是较小的。(因为当节点的左右子树只有一方为null时，返回较小的左右子树深度 + 1，会是0 + 1，但当前节点并非叶子节点，不该 从此处开始 计算最小深度，直接返回0 + 1，会导致上一层的以及最终的深度求解 错误。) import java.util.*; /* * public class TreeNode ...

0 点赞评论收藏

2023-01-09 16:26

西安理工大学 Java

题解 | #对称的二叉树#

二叉树对称，即以根节点所在为分界线，左右两半相等。根据二叉树对称的条件，可知 左子树的左子树和右子树的右子树，左子树的右子树和右子树的左子树，左子树和右子树的值相等才可。通过分析可知，使用递归 /* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { boolean i...

0 点赞评论收藏

2023-01-08 19:48

西安理工大学 Java

题解 | #二叉树的前序遍历#

前序遍历，即根左右。一般使用递归进行遍历在当前递归中处理根节点，下一层处理左节点，然后是右节点。且递归终结条件，若当前节点为空，则直接返回。 import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ public class Solution { /** ...

0 点赞评论收藏

2023-01-05 15:44

西安理工大学 Java

题解 | #删除链表的倒数第n个节点#

删除的前提是，确定节点位置。找到倒数第n个节点采用双指针的方式快指针先前进n个节点，然后慢指针从头开始，二者并行，直至快指针到达链表尾部此时，慢指针指向的，就是倒数第n个节点删除倒数第n个节点确定倒数第n+1个节点，即待删除节点node的前驱节点pre设置pre.next = node.next，即前驱节点的next更新为待删除节点的next综合以上，需要三个指针，一个快指针，一个待删除节点指针，一个前驱节点指针。同时，为了统一删除步骤，减少对特殊情况的排除(如，待删除节点是当前头节点)，这里预先设置一个虚拟头节点preHead，使前驱节点指向preHead。 import java.util...

0 点赞评论收藏

2022-11-12 00:12

已编辑

西安理工大学 Java

题解 | #二叉树的中序遍历#

中序遍历即 左根右，在左右子树遍历之间，将当前节点的值放入集合中。由于结果的大小未知，所以，使用集合去存储元素，最后再将集合转化为数组。import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ public class Solution { /** ...

0 点赞评论收藏

2022-11-11 23:47

已编辑

西安理工大学 Java

题解 | #二叉树的最大深度#

用后序遍历的方式，去获取最大深度import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Solution { /** * * @param root TreeNode类 * @return int整型 */ public int maxDepth (TreeNode root) { /...

0 点赞评论收藏

2022-08-05 21:18

西安理工大学 Java

题解 | #矩形覆盖#

画画图就明白了本质上还是斐波那契数列的变形 import java.util.*; public class Solution { public int rectCover(int target) { if (target == 0) { return 0; } int temp1 = 0, temp2 = 1, result = 0; for (int i = 1; i <= target; ++i) { result = temp1 + temp2; ...

0 点赞评论收藏

创作者周榜

关注他的用户也关注了：