前言 📢

本日记为个人的刷题学习日记,内容非原创,仅为自己复习知识时,能够看得懂自己写的CV的代码,快速理解题意。另外,👍力扣官方的题解很好用,三叶姐nb!!!!!

104. 二叉树的最大深度 ✅

题意

  • 给你一个二叉树的根结点root,判断该树的深度(层数)

思路

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public int maxDepth(TreeNode root) {
if(root == null) {
return 0; // 根节点为空 不存在 返回0
} else {
// 递归思路

// root的左子树 根节点为root.left 右子树根节点为root.right
// 找左右子树的层数最大值
int left = maxDepth(root.left);
int right = maxDepth(root.right);
return Math.max(left, right) + 1;
// 最后一次 返回左子树和右子树中最深的层数+1 (1为根节点层数)
// 在各个子树递归过程中,最后一层(left==null right==null 0+1=1)返回上一层、层层加一
}
}
}
/**
* Definition for a binary tree node.
* 定义了一个二叉树的节点结构
* public class TreeNode {
* int val; 当前节点值
* TreeNode left; 该节点的左孩子
* TreeNode right; 该节点的右孩子
* TreeNode() {}
* TreeNode(int val) { this.val = val; } this方法 给节点赋值
* 定义一个二叉树的方法
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/

98. 验证二叉搜索树 ✅

题意

  • 给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树

  • 二叉搜索树的定义:

    • 节点的左子树只包含 小于 当前节点的数。
    • 节点的右子树只包含 大于 当前节点的数。
    • 所有左子树和右子树自身必须也是二叉搜索树。
  • 简单说,对于任意一个节点,它的左子树内所有val小于该节点的val,它的右子树内所有val大于该节点的val,同时在左右孩子不为null的情况下,root.left.val < root.val < root.right.val

思路

中序遍历(二叉搜索树中序遍历后,得到的是一组严格递增的数)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
// 注意理解pre的含义 它始终指 当前访问的子树 的根节点的值
// 意在保证root.left.val < root.val
long pre = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {

if(root == null) {
return true;
}
// 中序遍历 左中右的顺序
// 左子树
if(!isValidBST(root.left)) { // 左子树不满足二叉搜索树的条件
return false;
}
// 中 即当前节点
if(root.val <= pre) {
return false;
}
pre = root.val;

// 访问右子树
return isValidBST(root.right);
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/

101.对称二叉树 ✅

题意

  • 判断给定的二叉树是否轴对称

思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 对于每一层 左子树根节点val == 右子树根节点val
// 同时 左子树的左孩子等于右子树的右孩子 左子树的右孩子等于右子树的左孩子
class Solution {
public boolean isSymmetric(TreeNode root) {
return dfs(root, root);
// 理解 dfs(root, root) 类似于将树根看成一个镜像 树根的左孩子等于树根的右孩子 树根的右孩子等于树根的左孩子
}

public boolean dfs(TreeNode rootLeft, TreeNode rootRight) {
if(rootLeft == null && rootRight == null) {
return true;
}

if(rootLeft == null || rootRight == null || rootLeft.val != rootRight.val) {
return false;
} else {
return dfs(rootLeft.left, rootRight.right) && dfs(rootLeft.right, rootRight.left);
}

}
}