算法训练营 day23 二叉树 修剪二叉搜索树 将有序数组转换为二叉搜索树 把二叉搜索树转换为累加树
修剪二叉搜索树
669. 修剪二叉搜索树 - 力扣（LeetCode）
给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。
所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。
递归法
- 确定递归函数的参数以及返回值
因为是要遍历整棵树，做修改，其实不需要返回值也可以，我们也可以完成修剪（其实就是从二叉树中移除节点）的操作。
但是有返回值，更方便，可以通过递归函数的返回值来移除节点。
- 确定终止条件
修剪的操作并不是在终止条件上进行的，所以就是遇到空节点返回就可以了。
- 确定单层递归的逻辑
如果root(当前节点)的元素小于low的数值，那么应该递归右子树，并返回右子树符合条件的头结点。
如果root(当前节点)的元素大于high的，那么应该递归左子树，并返回左子树符合条件的头结点。
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;}
}
迭代法
class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {if(root==null) return null;// 处理头结点，让root移动到[L, R] 范围内，注意是左闭右闭while (root!=null&&(root.val<low||root.val>high)){if (root.val<low) root = root.right;else if (root.val>high) root = root.left;}TreeNode cur = root;// 此时root已经在[L, R] 范围内，处理左孩子元素小于L的情况while (cur!=null){while (cur.left!=null&&cur.left.val<low){cur.left = cur.left.right;}cur = cur.left;}cur = root;// 此时root已经在[L, R] 范围内，处理右孩子大于R的情况while (cur!=null){while (cur.right!=null&&cur.right.val>high){cur.right = cur.right.left;}cur = cur.right;}return root;}
}
将有序数组转换为二叉搜索树
108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
本质就是寻找分割点，分割点作为当前节点，然后递归左区间和右区间。
递归法
class Solution {public TreeNode sortedArrayToBST(int[] nums) {return traversal(nums, 0, nums.length);}private TreeNode traversal(int[] nums, int left, int right) {if (left >= right) return null;if (right - left == 1) return new TreeNode(nums[left]);int mid = left + (right - left) / 2;TreeNode root = new TreeNode(nums[mid]);root.left = traversal(nums, left, mid);root.right = traversal(nums, mid + 1, right);return root;}
}
迭代法
class Solution {public TreeNode sortedArrayToBST(int[] nums) {if (nums.length==0) return null;TreeNode root = new TreeNode(-1);Queue<TreeNode> nodeque = new LinkedList();Queue<Integer> leftque = new LinkedList();Queue<Integer> rightque = new LinkedList();nodeque.add(root);leftque.add(0);rightque.add(nums.length);while (!nodeque.isEmpty()){TreeNode cur = nodeque.poll();int left = leftque.poll();int right = rightque.poll();int mid = left+(right-left)/2;cur.val = nums[mid];if (left<mid){cur.left = new TreeNode(-1);nodeque.add(cur.left);leftque.add(left);rightque.add(mid);}if (mid+1<right){cur.right = new TreeNode(-1);nodeque.add(cur.right);leftque.add(mid+1);rightque.add(right);}}return root;}
}
把二叉搜索树转换为累加树
538. 把二叉搜索树转换为累加树 - 力扣（LeetCode）
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
节点的左子树仅包含键 小于 节点键的节点。
节点的右子树仅包含键 大于 节点键的节点。
左右子树也必须是二叉搜索树。
其实这就是一棵树，大家可能看起来有点别扭，换一个角度来看，这就是一个有序数组[2, 5, 13]，求从后到前的累加数组，也就是[20, 18, 13]，是不是感觉这就简单了。
递归法
class Solution {int pre = 0;public TreeNode convertBST(TreeNode root) {traversal(root);return root;}private void traversal(TreeNode root) {if (root == null) return;traversal(root.right);root.val+=pre;pre = root.val;traversal(root.left);}
}
迭代法
class Solution {public TreeNode convertBST(TreeNode root) {if (root == null) return null;Stack<TreeNode> st =new Stack<>();st.push(root);TreeNode pre = null;int sum = 0;while (!st.isEmpty()){TreeNode node = st.pop();if (node!=null){if (node.left!=null) st.push(node.left);st.push(node);st.push(null);if (node.right!=null) st.push(node.right);}else {node = st.pop();if (pre!=null){node.val+=sum;}pre = node;sum = node.val;}}return root;}
}
