669. 修剪二叉搜索树

题目链接/文章讲解
这道题目比较难，比 添加增加和删除节点难的多，建议先看视频理解。

思路

public class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) return null;

//注意，不可以直接if(root > high || root.val < low) return null; 因为可能删除某个节点a，但是节点a的右孩子还在范围内

       if (root.val < low) {  //小于左边界，但是要删除的节点的右孩子可能符合边界，所以要继续向右遍历
            TreeNode right = trimBST(root.right, low, high); // 寻找符合区间[low, high]的节点
            return right; //递归向下遍历，子树不符合区间的都会被修剪
        }
        
        if (root.val > high) {
            TreeNode left = trimBST(root.left, low, high); // 寻找符合区间[low, high]的节点
            return left;  //如果递归返回null，会返回给移除节点的上一层，就相当于移除了这个节点
        }
        
        root.left = trimBST(root.left, low, high); // root.left接入符合条件的左孩子
        root.right = trimBST(root.right, low, high); // root.right接入符合条件的右孩子
        
        return root;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        // 示例测试用例
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(0);
        root.right = new TreeNode(4);
        root.left.right = new TreeNode(2);
        root.left.right.left = new TreeNode(1);

        int low = 1;
        int high = 3;
        TreeNode newRoot = solution.trimBST(root, low, high);

        printTree(newRoot); // 打印修剪后的树结构
    }

    // 辅助方法：打印二叉树
    public static void printTree(TreeNode root) {
        if (root != null) {
            printTree(root.left);
            System.out.print(root.val + " ");
            printTree(root.right);
        }
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

/**
 * 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 null;
        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;

    }
}

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 {
    //返回值TreeNode 代表返回构造平衡二叉搜索树的根节点
    //左右区间：左闭右闭还是左闭右开？ 这里是左闭右闭
    private TreeNode traversal(int[] nums, int left, int right) {
        if(left > right) return null;//终止条件

        //int mid = (left + right) / 2; //这里可能爆内存  但是本题中left right是数组里的下标，不可能爆内存
        int mid = ((right - left)/2) + left;

        //构造二叉树
        TreeNode root = new TreeNode(nums[mid]);
        //递归构造左右子树
        root.left = traversal(nums, left, mid - 1);
        root.right = traversal(nums, mid + 1, right);
        return root;

    }
    public TreeNode sortedArrayToBST(int[] nums) {
        return traversal(nums, 0, nums.length - 1);
    }
}

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

题目链接/文章讲解

思路

• 后序遍历再从后到前做一个累加。从最大的节点开始遍历：右中左。
• 如何把数值倒序相加：数组里会考虑双指针，一个pre一个cur，cur把pre的数值做一个相加。

/**
 * 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 int pre = 0; // 记录前一个节点的数值
    private void traversal(TreeNode cur){  //因为就是遍历和更新指针数值，所以不需要返回值
        if(cur == null) return; //没有返回值
        // 右中左遍历
        traversal(cur.right);
        cur.val += pre;
        pre = cur.val;
        traversal(cur.left);

    }
    public TreeNode convertBST(TreeNode root) {
        pre = 0;
        traversal(root);
        return root;
    }
}

总结篇

https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E6%80%BB%E7%BB%93%E7%AF%87.html

二刷记得再来总结……