Day21 ＞＞ 669、修剪二叉搜索树 + 108、将有序数组转换为二叉搜索树 + 538、把二叉搜索树转换为累加树

代码随想录-二叉搜索树

669、修剪二叉搜索树

1. 首先根据二叉搜索树的特性，寻找要修剪的节点
   1. 如果当前节点小于最小值，那么该节点需要修剪，继续往该节点的右子树遍历，因为该节点的左子树肯定都要被修剪掉了
   2. 同理，如果当前节点大于最大值，那么该节点需要修剪，继续往该节点的左子树遍历，因为该节点的右子树都要被修剪掉了
2. 子树修剪完成后，需要把修改后的子树的根节点往上返回

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、将有序数组转换为二叉搜索树

需要复习一下二叉树的构造了

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

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

class Solution { int sum = 0; public TreeNode convertBST(TreeNode root) { convert(root); return root; } private void convert(TreeNode root) { if (root == null) return ; convert(root.right); sum += root.val; root.val = sum; convert(root.left); } }

代码随想录-二叉树总结

周末记得复习下二叉树的总结