每日5题Day20 - LeetCode 96 - 100

每一步向前都是向自己的梦想更近一步，坚持不懈，勇往直前！

第一题：96. 不同的二叉搜索树 - 力扣（LeetCode）

class Solution {
    public int numTrees(int n) {
        if(n < 2){
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++){
            for(int j = 1; j <= i; j++){
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
}

第二题：97. 交错字符串 - 力扣（LeetCode）

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int len1 = s1.length(), len2 = s2.length(), len3 = s3.length();
        //长度肯定要相同
        if (len1 + len2 != len3) {
            return false;
        }
        
        boolean[][] dp = new boolean[len1 + 1][len2 + 1];
        dp[0][0] = true;
        //初始化一下，因为是boolean型dp数组，所以注意使用交集&&
        // 初始化第一行
        for (int j = 1; j <= len2; j++) {
            dp[0][j] = dp[0][j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
        }
        
        // 初始化第一列
        for (int i = 1; i <= len1; i++) {
            dp[i][0] = dp[i - 1][0] && s1.charAt(i - 1) == s3.charAt(i - 1);
        }
        //两种情况，任一满足均可
        // 动态规划求解
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) ||
                           (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
            }
        }
        
        return dp[len1][len2];
    }
}

第三题：98. 验证二叉搜索树 - 力扣（LeetCode）

/**
 * 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;
 *     }
 * }
 */
class Solution {
    private long preval = Long.MIN_VALUE;
    
    public boolean isValidBST(TreeNode root) {
        if(root == null){
            return true;
        }
        //对于每一个节点，左边成立是最基本的
        if(!isValidBST(root.left) || root.val <= preval){
            return false;
        }
        preval = root.val;
        //传入右边
        //注意遍历的顺序，其实是左->中->右这样来的
        //我们每次比较左边和中间，左边都是满足的时候比对中间和左边的值
        //如果仍然满足，我们可以调用右边节点继续遍历
        return isValidBST(root.right);
    }
}

class Solution {
    public boolean isValidBST(TreeNode root) {
        //这个做法会出现错误
        //原因是错误的节点结果无法传递上去，
        //所以从根节点出发遍历一次正确了就会返回正确
        if(root.left != null){
            if(root.left.val < root.val){
                isValidBST(root.left);
            }
            else{
                return false;
            }
        }
        if(root.right != null){
            if(root.right.val > root.val){
                isValidBST(root.right);
            }
            else{
                return false;
            }
        }
        return true;
    }
}

class Solution {
    public boolean isValidBST(TreeNode root) {
        //和上一题一样，是想要针对每一个点来讨论
        //重载一下函数，在每次比对的时候传入左右节点的值
        return isValidBST(root, null, null);
    }
    
    private boolean isValidBST(TreeNode node, Integer min, Integer max) {
        if (node == null) return true;
        
        if ((min != null && node.val <= min) || (max != null && node.val >= max)) {
            return false;
        }
        
        return isValidBST(node.left, min, node.val) && isValidBST(node.right, node.val, max);
    }
}

第四题：99. 恢复二叉搜索树 - 力扣（LeetCode）

class Solution {
    TreeNode first = null;  // 第一个错误的节点
    TreeNode second = null; // 第二个错误的节点
    TreeNode prev = null;   // 用于记录前一个节点

    public void recoverTree(TreeNode root) {
        // 中序遍历二叉搜索树，找到两个错误节点
        inorder(root);
        
        // 交换两个错误节点的值
        int temp = first.val;
        first.val = second.val;
        second.val = temp;
    }

    private void inorder(TreeNode node) {
        if (node == null) return;

        // 遍历左子树
        inorder(node.left);

        // 处理当前节点
        if (prev != null && prev.val > node.val) {
            // 找到第一个错误的节点
            if (first == null) {
                first = prev;
            }
            // 找到第二个错误的节点
            second = node;
        }
        prev = node; // 更新 prev

        // 遍历右子树
        inorder(node.right);
    }
}

 第五题：100. 相同的树 - 力扣（LeetCode）

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null){
            return true;
        }
        if((p != null && q == null) || (p == null && q!= null) || p.val != q.val){
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}