『LeetCode』#1刷题日记

前言 📢

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

104. 二叉树的最大深度 ✅

题意

• 给你一个二叉树的根结点root，判断该树的深度（层数）

思路

递归

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

思路

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

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.对称二叉树 ✅

题意

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

思路

// 对于每一层 左子树根节点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);
        }
        
    }
}