【算法刷题day23】Leetcode:669. 修剪二叉搜索树、108. 将有序数组转换为二叉搜索树、538. 把二叉搜索树转换为累加树

草稿图网站
java的Deque

Leetcode 669. 修剪二叉搜索树

题目：669. 修剪二叉搜索树
解析：代码随想录解析

解题思路

对于不符合的节点，如果该节点小于区间，则右孩子可能符合；如果该节点大于区间，则左孩子可能符合。

代码

/**
 * 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 trimBST(TreeNode root, int low, int high) {
        if (root == null)
            return root;
        if (root.val < low) {
            return trimBST(root.right, low, high);
        }
        if (root.val > high) {
            return trimBST(root.left, low, high);
        }
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }
}

//迭代法
class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null)
            return root;
        while (root != null && (root.val < low || root.val > high)) {
            if (root.val < low)
                root = root.right;
            else
                root = root.left;
        }

        TreeNode cur = root;
        while (cur != null) {
            while (cur.left != null && cur.left.val < low)
                cur.left = cur.left.right;
            cur = cur.left;
        }
        cur = root;
        while (cur != null) {
            while (cur.right != null && cur.right.val > high)
                cur.right = cur.right.left;
            cur = cur.right;
        }
        return root;
    }
}

总结

暂无

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

题目：108. 将有序数组转换为二叉搜索树
解析：代码随想录解析

解题思路

递归+数组

代码

/**
 * 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) {
        if (nums == null || nums.length == 0)
            return null;
        return buildTree(nums, 0, nums.length);
    }
    private TreeNode buildTree(int[] nums, int left, int right) {
        if (left == right)
            return null;
        if (left + 1 == right)
            return new TreeNode(nums[left]);
        int mid = left + (right - left) / 2;
        TreeNode midNode = new TreeNode(nums[mid]);
        midNode.left = buildTree(nums, left, mid);
        midNode.right = buildTree(nums, mid + 1, right);
        
        return midNode;
    }
}

总结

迭代懒得写了

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

题目：538. 把二叉搜索树转换为累加树
解析：代码随想录解析

解题思路

反过来的中序

代码

/**
 * 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 {
    int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        if (root == null)
            return null;
        order(root);
        return root;
    }
    private void order(TreeNode node) {
        if (node == null)
            return;
        order(node.right);
        sum += node.val;
        node.val = sum;
        order(node.left);
    }
}

总结

递归懒得写