作者： CheungQ

二叉树数据结构TreeNode可用来表示单向链表（其中left置空，right为下一个链表节点）。实现一个方法，把二叉搜索树转换为单向链表，要求依然符合二叉搜索树的性质，转换操作应是原址的，也就是在原始的二叉搜索树上直接修改。

返回转换后的单向链表的头节点。

注意：本题相对原题稍作改动

示例：

输入： [4,2,5,1,3,null,6,0]
输出： [0,null,1,null,2,null,3,null,4,null,5,null,6]

提示：

• 节点数量不会超过 100000。

题解

很明显，二叉搜索树转换成的是有序递增链表，直接用DFS中序遍历处理。

需要两个变量，一个用来记录一开始访问到的新的头结点位置，另一个用来记录在DFS过程中上次遍历到的节点，及该节点的前驱节点。

按照题目的要求，在遍历过程中重新指向节点之间新的left、right指向关系，而不重新生成新的节点。

另外，最后记得清空下最后的节点的左右子节点

current.left = null;
current.right = null;

当二叉树的右子树最末端是这样的情况的时候

       …
         \
          5
         /
        4

4节点先被加入到节点结尾，4节点的left被指向null，right指向到5。

5节点最后被加入到结尾，此时5的left还是指向到4，需要再去清除下关系。

当然可以在dfs中处理一下也是可以的。

//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    private TreeNode head;
    private TreeNode current;
    public TreeNode convertBiNode(TreeNode root) {
        if (null == root)return null;
        dfs(root);
        current.left = null;
        current.right = null;
        return head;
    }

    private void dfs(TreeNode root){
        if (root.left!=null){
            dfs(root.left);
        }
        if (head ==null){
            head = root;
        }
        if (current!=null){
            current.left = null;
            current.right = root;
        }
        current = root;
        if (root.right!=null){
            dfs(root.right);
        }
    }


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

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：

输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。

示例 2：

输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。

提示：

• 1 <= s.length <= 1000
• s 仅由小写英文字母组成

题解

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int longestPalindromeSubseq(String s) {
        int[][] dp = new int[s.length()][s.length()];
        for (int i = s.length() - 1; i >= 0; i--) {
            dp[i][i] = 1;
            for (int j = i + 1; j < s.length(); j++) {
                if (s.charAt(i)==s.charAt(j)){
                    dp[i][j] = dp[i+1][j-1]+2;
                }else{
                    dp[i][j] = Math.max(dp[i][j],Math.max(dp[i+1][j],dp[i][j-1]));
                }
            }
        }

        return dp[0][s.length()-1];
    }
}
//leetcode submit region end(Prohibit modification and deletion)

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

• 节点的左子树只包含小于当前节点的数。
• 节点的右子树只包含大于当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:
    2
   / \
  1   3
输出: true

示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

题解

一样的，中序遍历，然后当前值要比前驱值大。不要求验证平衡，一开始没注意还加了平衡验证有点费事。

/**
 * 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 Integer lastNum;
    boolean valied = false;

    public boolean isValidBST(TreeNode root) {
        return dfs(root)==1;
    }


    private int dfs(TreeNode root){
        if (valied){
            return 0;
        }
        int left = 1;
        int right = 1;
        if (root.left != null){
            left = dfs(root.left);
        }
        if (lastNum!=null && lastNum >= root.val){
            valied = true;
            return 0;
        }
        lastNum = root.val;
        if (root.right != null){
            right = dfs(root.right);
        }
        return left & right;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

给你一个整数数组 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)