代码随想录算法训练营第二十天-669修剪二叉搜索树、108将有序数组转换为二叉搜索树、538把二叉搜索树转换为累加树

前言
状态：669 通过，但是有更简单的方法。108AC。538 没有思路，看了解题思路写出来了。
更新

1	24-06-09 初始记录

初步题解

669 修剪二叉搜索树

题目链接：(https://leetcode.cn/problems/trim-a-binary-search-tree)

	/**
     * 思路：查找节点，删除节点
     * 
     * @param root 根节点
     * @param low  区间左范围
     * @param high 区间右范围
     * @return
     */
    public static TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) {
            return root;
        }
        // 先剪枝
        cut(root, low, high);
        // 再减单个
        return travel(root, low, high);
    }

    private static TreeNode travel(TreeNode root, int low, int high) {
        if (root == null) {
            return root;
        }

        if (low <= root.val && root.val <= high) {
            root.left = travel(root.left, low, high);
            root.right = travel(root.right, low, high);
        } else {
            if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            } else {
                // 删除这个节点
                // 1.右子树补位(找到右子树的最左侧节点)
                TreeNode cur = root.right;
                while (cur.left != null) {
                    cur = cur.left;
                }
                cur.left = root.left;
                root = root.right;

                return root;
            }
        }

        root.left = travel(root.left, low, high);
        root.right = travel(root.right, low, high);
        return root;
    }

    private static void cut(TreeNode root, int low, int high) {
        if (root == null) {
            return;
        }

        // 整条剪掉
        if (root.val > high) {
            root.right = null;
            root.left = trimBST(root.left, low, high);
        }
        if (root.val < low) {
            root.left = null;
            root.right = trimBST(root.right, low, high);
        }
        cut(root.left, low, high);
        cut(root.right, low, high);
    }

// 因为时间复杂度太高，后面又写了一个版本，但是这个版本AC不了
public static TreeNode trimBST(TreeNode root, int low, int high) {  
        if (root == null) {  
            return root;  
        }  
  
        if (root.val > high) {  
			return root.left;  
            // return trimBST(root.left, low, high);  
        }  
        if (root.val < low) {  
            // 继续向右遍历  
			return root.right;  
            // return trimBST(root.right, low, high);  
        }  
  
        if (low <= root.val && root.val <= high) {  
            root.left = trimBST(root.left, low, high);  
            root.right = trimBST(root.right, low, high);  
        }  
  
        while (root != null && (root.val < low || root.val > high)) {  
            if (root.left == null) {  
                root = root.right;  
            } else if (root.right == null) {  
                root = root.left;  
            } else {  
                // 删除这个节点  
                // 1.右子树补位(找到右子树的最左侧节点)  
                TreeNode cur = root.right;  
                while (cur.left != null) {  
                    cur = cur.left;  
                }  
                cur.left = root.left;  
                root = root.right;  
            }  
        }  
        return root;  
    }

108 将有序数组转换为二叉搜索树

题目链接：(https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/)

public static TreeNode sortedArrayToBST(int[] nums) {  
    if (nums.length == 0) {  
        return null;  
    }  
    return sortedDFS(nums, 0, nums.length);  
}  
  
private static TreeNode sortedDFS(int[] nums, int i, int j) {  
    if (i >= j) {  
        return null;  
    }  
  
    int mid = (j - i) / 2 + i;  
    TreeNode treeNode = new TreeNode(nums[mid]);  
    treeNode.left = sortedDFS(nums, i, mid);  
    treeNode.right = sortedDFS(nums , mid + 1, j);  
    return treeNode;  
}

538 把二叉搜索树转换为累加树

题目链接：(https://leetcode.cn/problems/convert-bst-to-greater-tree)

/**  
 * 看了题解之后写出来的  
 * 思路：  
 * 1.二叉搜索树，中序遍历（左中右）有序  
 * 2.要按倒序相加，遍历方向相反  
 * 3.取一个指针指向前节点不断累加  
 */  
TreeNode pre = new TreeNode(0);  
public TreeNode convertBST(TreeNode root) {  
    getTreeNodeTravel(root);  
    return root;  
}  
  
private void getTreeNodeTravel(TreeNode root) {  
    if (root == null) {  
        return;  
    }  
  
    getTreeNodeTravel(root.right);  
  
    root.val = pre.val + root.val;  
    pre = root;  
    getTreeNodeTravel(root.left);  
}

看解析

669 修剪二叉搜索树

题目链接/文章讲解： https://programmercarl.com/0669.%E4%BF%AE%E5%89%AA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html

视频讲解： [https://www.bilibili.com/video/BV17P41177ud](https://www.bilibili.com/video/BV17P41177ud

看了题解发现是下面两行导致不能 AC。这里不能直接剪掉，忽略了情况。

并且用了下面的继续递归，就不用再删除节点了。

if (root.val > high) {  
	return root.left;  
    // return trimBST(root.left, low, high);  
}  
if (root.val < low) {  
    // 继续向右遍历  
	return root.right;  
    // return trimBST(root.right, low, high);  
}

正确方法（🥴好难）：

public static TreeNode trimBST(TreeNode root, int low, int high) {  
    if (root == null) {  
        return root;  
    }  
    if (root.val > high) {  
        return trimBST(root.left, low, high);  
    }  
    if (root.val < low) {   
        return trimBST(root.right, low, high);  
    }  
    if (low <= root.val && root.val <= high) {  
        root.left = trimBST(root.left, low, high);  
        root.right = trimBST(root.right, low, high);  
    }  
    return root;  
}

108 将有序数组转换为二叉搜索树

题目链接/文章讲解： https://programmercarl.com/0108.%E5%B0%86%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E8%BD%AC%E6%8D%A2%E4%B8%BA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html

视频讲解：[https://www.bilibili.com/video/BV1uR4y1X7qL](https://www.bilibili.com/video/BV1uR4y1X7qL

538 把二叉搜索树转换为累加树

题目链接/文章讲解： https://programmercarl.com/0538.%E6%8A%8A%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E8%BD%AC%E6%8D%A2%E4%B8%BA%E7%B4%AF%E5%8A%A0%E6%A0%91.html

视频讲解：https://www.bilibili.com/video/BV1d44y1f7wP