每日算法Day14【删除二叉搜索树中的节点、修剪二叉搜索树、将有序数组转换为二叉搜索树、把二叉搜索树转换为累加树】

450.删除二叉搜索树中的节点

算法链接:

450. 删除二叉搜索树中的节点 - 力扣（LeetCode）
类型: 二叉树
难度: 中等

思路：两层判断，第一层判断节点与key大小，如果节点删除则判断其左右子节点情况；如果只有一个子节点，移动指针指向下一个节点；如果都不为空，则将该节点的左节点转移到别处。

题解:

/**
 * 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 root;
    if (root.val == key) {
      if (root.left == null) {
        return root.right;
      } else if (root.right == null) {
        return root.left;
      } else {
        TreeNode cur = root.right;
        while (cur.left != null) {
          cur = cur.left;
        }
        cur.left = root.left;
        root = root.right;
        return root;
      }
    }
    if (root.val > key) root.left = deleteNode(root.left, key);
    if (root.val < key) root.right = deleteNode(root.right, key);
    return root;
  }
}

669. 修剪二叉搜索树

算法链接:

669. 修剪二叉搜索树 - 力扣（LeetCode）
类型: 二叉树
难度: 中等

题解:

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

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

算法链接:

108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）
类型: 二叉树
难度: 简单

题解:

/**
 * 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) {
        TreeNode root = new TreeNode(nums[nums.length/2]);
        root = build(nums,0,nums.length-1);
        return root;
    }

    TreeNode build(int[] nums,int left,int right){
        if(left>right){
            return null;
        }
        int mid = (-left+right)/2+left;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = build(nums,left,mid-1);
        root.right = build(nums,mid+1,right);
        return root;
    }
}

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

算法链接:

538. 把二叉搜索树转换为累加树 - 力扣（LeetCode）
类型: 二叉树
难度: 中等

题解:

/**
 * 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 root;
        }
        TreeNode r = convertBST(root.right);
        sum+=root.val;
        root.val = sum;
        TreeNode l = convertBST(root.left);
        return root;
    }
}