算法刷题日志——二叉树

删除二叉搜索树中的节点

递归来解这道题（以下是宫水三叶的题解，写的太妙了！
https://leetcode.cn/problems/delete-node-in-a-bst/solutions/1531428/by-ac_oier-s60a/）
根据当前 root.val 与 key 的大小关系，进行分情况讨论：
若有 root.val 若有 root.val>keyroot.val > keyroot.val>key，说明待删除的节点必然不是当前节点，以及不在当前节点的右子树，我们将删除节点「递归」到当前节点的左子树，并将删除（可能进行）之后的新的左子树根节点，重新赋值给 root.left，即有 root.left = deleteNode(root.left, key)；
若有 root.val=keyroot.val = keyroot.val=key，此时找到了待删除的节点，我们根据左右子树的情况，进行进一步分情况讨论：
若左/右子树为空，我们直接返回右/左子树节点即可（含义为直接将右/左子树节点搬到当前节点的位置）如图所示：
若左右子树均不为空，我们有两种选择：
从「当前节点的左子树」中选择「值最大」的节点替代 root 的位置，确保替代后仍满足 BST 特性；
从「当前节点的右子树」中选择「值最小」的节点替代 root 的位置，确保替代后仍满足 BST 特性；
我们以「从当前节点的左子树中选择值最大的节点」为例子，我们通过树的遍历，找到其位于「最右边」的节点，记为 ttt（ttt 作为最右节点，必然有 t.right = null），利用原本的 root 也是合法 BST，原本的 root.right 子树的所有及节点，必然满足大于 t.val，我们可以直接将 root.right 接在 t.right 上，并返回我们重接后的根节点，也就是 root.left。

直接将整个右子树挂在左子树最大值上，省事很多。

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;//空直接返回空节点
        if (root.val == key) {
            if (root.left == null) return root.right;
            if (root.right == null) return root.left;
            TreeNode t = root.left;
            while (t.right != null) t = t.right;//当前节点
            t.right = root.right;
            return root.left;
        } else if (root.val < key) root.right = deleteNode(root.right, key);
        else root.left = deleteNode(root.left, key);
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

修剪二叉搜索树

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);
        else 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;
    }
}


1
2
3
4
5
6
7
8
9
10
11
12

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

因为是二叉搜索树，那么数组已经排好序了，那么就取中间点作为根节点，然后进行中序遍历，来进行递归构建。

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
            return dfs(nums,0,nums.length-1);
    }
        private TreeNode dfs(int[] nums,int low,int high){
                if(low>high)return null;
                int mid=low+(high-low)/2;
                TreeNode root =new TreeNode(nums[mid]);
                root.left=dfs(nums,low,mid-1);
                root.right=dfs(nums,mid+1,high);
                return root;
        }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

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

其实这个题就是找比自己大的节点并且加和。
中序遍历的顺序是左子树、根节点、右子树，这个顺序转换在二叉搜索树中，其实就是先找到二叉搜索树中最大的值，也就是整棵二叉搜索树右下角的值。，其实就是二叉搜索树反着中序遍历来，即遍历的顺序为：右子树、根节点、左子树，同时按照这个顺序累加就行了。

class Solution {
    // 记录前一个节点的累加值
    int preSum;
    public void nodeSum(TreeNode root){
        if(root == null){
            return ;
        }
        // 遍历右子树
        nodeSum(root.right);
        // 对节点值累加
        root.val += preSum;
        // 更新 preSum 值
        preSum = root.val;
        // 遍历左子树
        nodeSum(root.left);
    }

    public TreeNode convertBST(TreeNode root) {
        preSum = 0;
        nodeSum(root);
        return root;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24