月度归档： 2021年8月

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1：

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：

输入：nums = [1,3]
输出：[3,1]
解释：[1,3] 和 [3,1] 都是高度平衡二叉搜索树。

提示：

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 按 严格递增 顺序排列

题解

简单题，不再做额外解释，具体可以参看前一篇LeetCode刷题【1382】将二叉搜索树变平衡，里面包含了本题内容

/**
 * 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 {
    public TreeNode sortedArrayToBST(int[] nums) {
        return createTree(nums, 0, nums.length-1);
    }

    TreeNode createTree(int[] nums,int left, int right){
        if (right<left)return null;
        int mid = (left+right)>>1;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = createTree(nums,left,mid-1);
        node.right = createTree(nums,mid+1,right);
        return node;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

给你一棵二叉搜索树，请你返回一棵 平衡后 的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。

如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 1 ，我们就称这棵二叉搜索树是 平衡的 。

如果有多种构造方法，请你返回任意一种。

示例：

输入：root = [1,null,2,null,3,null,4,null,null]
输出：[2,1,3,null,null,null,4]
解释：这不是唯一的正确答案，[3,1,4,null,2,null,null] 也是一个可行的构造方案。

提示：

• 树节点的数目在 1 到 10^4 之间。
• 树节点的值互不相同，且在 1 到 10^5 之间。

题解

最直观的思路解法，因为本身给出的是一个二叉搜索树，但是不平衡，所以可以直接进行中序遍历，拿到一个递增的list，再用这个list直接构建一个新的平衡二叉树就可以了

import java.util.ArrayList;

/**
 * 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 List<Integer> list = new ArrayList<>();
    public TreeNode balanceBST(TreeNode root) {
        //先取到中序遍历结果，
        dsf(root);

        return createBST(0,list.size()-1);
    }

    private void dsf(TreeNode root){
        if(root.left!=null)dsf(root.left);
        list.add(root.val);
        if(root.right!=null)dsf(root.right);
    }

    private TreeNode createBST(int left, int right){
        if (right < left) return null;
        int mid = (left + right)>>1;
        TreeNode node = new TreeNode(list.get(mid));
        node.left = createBST(left,mid-1);
        node.right = createBST(mid+1,right);
        return node;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

根据特性，数组的中间一位为root节点，左边为左子树上的中序遍历结果，右边为右子树上的中序遍历结果，所以可以直接取中间一位作为根节点，左边的集合和右边的集合分别递归构建即可。

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

1. 首先找到需要删除的节点；
2. 如果找到了，删除它。

说明： 要求算法时间复杂度为 O(h)，h 为树的高度。

示例:

root = [5,3,6,2,4,null,7]
key = 3

    5
   / \
  3   6
 / \   \
2   4   7

给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。

一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。

    5
   / \
  4   6
 /     \
2       7

另一个正确答案是 [5,2,6,null,4,null,7]。

    5
   / \
  2   6
   \   \
    4   7

题解

/**
 * 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 {
    public TreeNode deleteNode(TreeNode root, int key) {
        //最终空节点判断
        if (root==null)return null;
        if (key < root.val){
            //在左子树中继续找了删除key
            root.left = deleteNode(root.left,key);
        }else if ( key > root.val){
            //在右子树中找了删除key
            root.right = deleteNode(root.right,key);
        }else{
            //找到了这个节点
            //如果没有子节点，直接删除当前节点，如果只有一个子节点，把子节点放到当前位置
            if (root.left == null || root.right == null){
                return root.left==null ? root.right : root.left;
            }else{
                //肯定有两个子节点的情况
                TreeNode node = getPre(root);
                //这里取前驱结点的值，给到root节点上
                root.val = node.val;
                //在左子树上删掉移动上来的前驱节点
                root.left = deleteNode(root.left,node.val);
            }
        }
        return root;
    }



    //找到前驱节点
    private TreeNode getPre(TreeNode root){
        TreeNode node = root.left;
        while (node.right!=null){
            node = node.right;
        }
        return node;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

BST的删除基本操作，相关BST的更多操作概念回头补上

给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。

假定 BST 有如下定义：

• 结点左子树中所含结点的值小于等于当前结点的值
• 结点右子树中所含结点的值大于等于当前结点的值
• 左子树和右子树都是二叉搜索树

例如：
给定 BST [1,null,2,2],

   1
    \
     2
    /
   2

返回[2].

提示：如果众数超过1个，不需考虑输出顺序

进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

题解

根据题意，这棵BST树如果按照中序遍历的结果大概应该是这样的

[1,1,1,2,3,3,3,5,5,5,5,5,6,7]

这样再来看这道题的话是不是就看起来很好处理了。把原本数组遍历for循环的方法替换成中序遍历dfs方法，剩下的就是当前位置和前一位置比较，统计数量，和最长序列的数量对比。

如果和最长序列的长度相同，则加入结果集res中。

如果比最长序列的长度还长，则更新当前长度为最长序列，并把结果集res清空，再将当前值加入结果集中。

import java.util.ArrayList;
import java.util.List;

/**
 * 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 final List<Integer> list = new ArrayList<>();
    private Integer lastNum;
    private int maxCount = 0;
    private int currentCount;
    public int[] findMode(TreeNode root) {
        dfs(root);
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    private void dfs(TreeNode root){
        if (root==null)return;
        dfs(root.left);
        countNum(root.val);
        dfs(root.right);
    }

    private void countNum(Integer rootNum){
        if (!rootNum.equals(lastNum)){
            lastNum = rootNum;
            currentCount = 1;
        }else{
            currentCount++;
        }
        if (currentCount > maxCount){
            maxCount = currentCount;
            list.clear();
            list.add(rootNum);
        }else if (currentCount == maxCount){
            list.add(rootNum);
        }
    }

}
//leetcode submit region end(Prohibit modification and deletion)

如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。

• 例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。

输入：nums = [1,2,3,4]
输出：3
解释：nums 中有三个子等差数组：[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。

输入：nums = [1]
输出：0

题解

8月10日每日一题

这题比较简单，题目中已经说明了，给出的int[] nums必定是符合条件的分段等差数列，所以，我们其实要做的就是找出各个分段之间的界限，分别求出各个分段的子序列数量并求和。

那么。如果想要在一次遍历中完成这样的操作，我们需要记录几个关键的信息

1. 当前位置和上一个位置的数字的差值（i位置和i-1位置的差值）
2. 上一个位置和上上一个的差值（i-1和i-2位置）
3. 如果这两个值相等则表示当前数字仍然在同一个等差区间之中，如果不等，则表示已经进入了一个新的等差区间
4. 还有一个重要的信息，就是当前等差区间的开始位置

接下来分情况讨论。

• 如果不等于：表明当前位置是处于两个不同等差分段相接的部分。需要更新差值信息和分段起始位置。

按照逻辑来说，当前位置应当是分段起始位置。比如[1,2,3,8,9,10]的数组，当我们到达数字8的索引3的时候，知道了起始位置为3。8和前面的值3的差值为5，而当我们到达数字9的时候，9和8的差值为1，是不是应该重新记录分段开始位置呢？显然是错误的，本题中要求子序列最短长度为3，所以只有到达9的时候我们才会知道分段起始位置应该为8所在的位置。

如果9后面的值不是10，那么分段起始位置会重新刷新，如果是10，那么满足了上面的i – （i-1） 等于 （i-1）-（i-2）位置的值，则恰好分段开始位置为8所在的位置。

• 如果是值等于的情况

本来写了长度判断，但是再看了下，能进入这个条件的，必定是长度至少为3的等差分段区间。然后求出当前区间的子序列个数最终求和。

我们来看下，设等差区间的长度为k

当k=3的时候，子序列个数为1

当k=4的时候，子序列个数为1（自身4个）+2（长度为3的2个子序列）

当k=5的时候，子序列个数为1（自身5个）+2（长度为4的2个子序列）+3（长度为3的3个子序列）

当k=6的时候，子序列个数为1（自身6个）+2（长度为5的2个子序列）+3（长度为4的3个子序列）+4（长度为3的4个子序列）

所以，其实很明白了，就是从1开始到指定数字的求和公式n(n+1)/2

但是这边的合是一次性的，而我们的计算是遍历中求的，不可能当我们还在i点的时候就知道有当前等差分段区间终止位置为i+i’位置，（当然也可以选择在找到3个连续的等差数字的之后往后探测找到结尾位置）。所以我们在遍历中需要在n位置得到总数后，再减去前面一次多加了的，即（n(n+1)/2）-（n(n-1)/2）= n。

这样就很简单明了了，当差区间的长度k=3的时候只需总数+1，k=4的时候只需总数再加2，k=5的之后总数再加3，以此类推。

代码：

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        if (nums.length<3){
            return 0;
        }
        int dis = 0;
        int sum = 0;
        int lastDis = nums[1]-nums[0];
        int disIndexStart = 0;
        for (int i = 2; i < nums.length; i++) {
            dis = nums[i]-nums[i-1];
            if (dis != lastDis){
                lastDis = dis;
                disIndexStart = i-1;
                continue;
            }else{
                //if (i-disIndexStart >= 2){
                    //超过三个了
                    sum+=i-disIndexStart-1;
                //}
            }
        }
        return sum;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:36 MB,击败了87.74% 的Java用户

题目：力扣挂了。。蛋疼

题目内容后续再补上Html版的

设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。 
如果指定节点没有对应的“下一个”节点，则返回null。 
示例 1: 
输入: root = [2,1,3], p = 1

  2
 / \
1   3

输出: 2

 示例 2:

 输入: root = [5,3,6,2,4,null,null,1], p = 6

      5
     / \
    3   6
   / \
  2   4
 /
1

输出: null
 Related Topics 树 深度优先搜索 二叉搜索树 二叉树
 👍 71 👎 0

题解

按照题意，找的就是二叉树按照中序遍历，排在目标节点后面一位的数字，这个节点可能是目标节点的右子节点，也还有可能是目标节点的父节点（当目标节点作为父节点的左子节点，且没有右子节点的时候）。

所以按照题意，直接DFS写个中序遍历，找到目标节点后，标记下已经找到目标节点，而在遍历下一个节点之前判断下，是否已经找到目标节点，如果已经找到了目标节点，则此时需要遍历的节点便是后继者节点。

class Solution {

    private TreeNode current;
    private TreeNode follower;

    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        midFetch(root,p);
        return follower;
    }

    private void midFetch(TreeNode root , TreeNode p){
        if (root==null)return;
        if (follower!=null){
            return ;
        }
        midFetch(root.left,p);
        if (follower!=null){
            return ;
        }
        if (current!=null && current.val == p.val ){
            follower = root;
            return ;
        }
        current = root;
        midFetch(root.right,p);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

题中左子节点遍历完成之后需要判断下follower!=null，这里一开始没注意，踩了个坑，在官方给出的测试用例中

测试用例:[5,3,6,2,4,null,null,1]
1

如果没有此处的判断，则会跑出错误的答案。按照规则，应当是每遍历一个节点之后都需要判断。

所以左子节点遍历后需要判断一下，root节点遍历的时候需要判断一下，右子节点遍历的时候也需要判断一下，但是因为右子节点已经在方法结尾，所以省去判断。