wordpress新闻站自动采集器网络促销策略

235.二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

• 所有节点的值都是唯一的。
• p、q 为不同节点且均存在于给定的二叉搜索树中。

代码 

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {// 基本情况：如果根节点为空，返回空if (root == null) {return null;}// 如果p和q的值都大于根节点，最近公共祖先在右子树if (p.val > root.val && q.val > root.val) {return lowestCommonAncestor(root.right, p, q);}// 如果p和q的值都小于根节点，最近公共祖先在左子树if (p.val < root.val && q.val < root.val) {return lowestCommonAncestor(root.left, p, q);}// 如果一个节点值较小而另一个较大，或者一个等于根节点// 那么当前根节点就是最近公共祖先return root;}
}

701.二叉搜索树中的插入操作

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

示例 1：

输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]
解释：另一个满足题目要求可以通过的树是：

示例 2：

输入：root = [40,20,60,10,30,50,70], val = 25
输出：[40,20,60,10,30,50,70,null,null,25]

示例 3：

输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
输出：[4,2,7,1,3,5]

提示：

• 树中的节点数将在 [0, 104]的范围内。
• -108 <= Node.val <= 108
• 所有值 Node.val 是 独一无二 的。
• -108 <= val <= 108
• 保证 val 在原始BST中不存在。

 代码

class Solution {public TreeNode insertIntoBST(TreeNode root, int val){return insertIntoBST1(root,val,root);}public TreeNode insertIntoBST1(TreeNode root, int val,TreeNode head) {if(root==null){TreeNode answer=new TreeNode(val);return answer;}if(root.val<val){  // 右子树插入if(root.right!=null){return insertIntoBST1(root.right,val,head);}else{root.right=new TreeNode(val);return head;}}else{if(root.left!=null){return insertIntoBST1(root.left,val,head);}else{root.left=new TreeNode(val);return head;}}}
}

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

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

1. 首先找到需要删除的节点；
2. 如果找到了，删除它。

示例 1:

输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]
解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。

示例 2:

输入: root = [5,3,6,2,4,null,7], key = 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0 的节点

示例 3:

输入: root = [], key = 0
输出: []

提示:

• 节点数的范围 [0, 104].
• -105 <= Node.val <= 105
• 节点值唯一
• root 是合法的二叉搜索树
• -105 <= key <= 105

进阶： 要求算法时间复杂度为 O(h)，h 为树的高度。

代码

 

class Solution {TreeNode deleteNode(TreeNode root, int key) {if (root == null) return null;return deleteNode1(root, key);}TreeNode deleteNode1(TreeNode root, int key) {if (root == null) return null;if (root.val < key) {root.right = deleteNode1(root.right, key);} else if (root.val > key) {root.left = deleteNode1(root.left, key);} else { // 找到删除节点// 情况1：无子节点if (root.left == null && root.right == null) return null;// 情况2：只有一个子节点if (root.left == null) return root.right;if (root.right == null) return root.left;// 情况3：两个子节点TreeNode successor = findMin(root.right); // 找右子树最小值root.val = successor.val; // 替换值root.right = deleteNode1(root.right, successor.val); // 删除后继}return root;}TreeNode findMin(TreeNode node) {while (node.left != null) {node = node.left;}return node;}
}

669.修剪二叉搜索树

给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

示例 1：

输入：root = [1,0,2], low = 1, high = 2
输出：[1,null,2]

示例 2：

输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
输出：[3,2,null,1]

提示：

• 树中节点数在范围 [1, 104] 内
• 0 <= Node.val <= 104
• 树中每个节点的值都是 唯一 的
• 题目数据保证输入是一棵有效的二叉搜索树
• 0 <= low <= high <= 104

代码

class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {root=trimBST1(root,low,high);return root;}public TreeNode trimBST1(TreeNode root, int low, int high) {if(root==null) return null;if(root.val<=high && root.val>=low){root.left=trimBST1(root.left,low,high);root.right=trimBST1(root.right,low,high);return root;}else if(root.val<low){return trimBST1(root.right,low,high);}else{return trimBST1(root.left,low,high);}}
}

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

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。

示例 1：

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：

输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

提示：

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 按 严格递增 顺序排列

代码

 

class Solution {public TreeNode sortedArrayToBST(int[] nums) {// 如果数组为空，返回 nullif (nums == null || nums.length == 0) {return null;}// 调用递归辅助函数，处理整个数组return buildBST(nums, 0, nums.length - 1);}// 递归辅助函数，构建 BSTprivate TreeNode buildBST(int[] nums, int left, int right) {// 基线条件：如果 left > right，说明子数组为空，返回 nullif (left > right) {return null;}// 选择中间元素作为根节点int mid = left + (right - left) / 2; // 避免整数溢出TreeNode root = new TreeNode(nums[mid]);// 递归构建左子树（左半部分）root.left = buildBST(nums, left, mid - 1);// 递归构建右子树（右半部分）root.right = buildBST(nums, mid + 1, right);// 返回当前子树的根节点return root;}
}

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

给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

• 节点的左子树仅包含键 小于 节点键的节点。
• 节点的右子树仅包含键 大于 节点键的节点。
• 左右子树也必须是二叉搜索树。

注意：本题和 1038: 1038. 从二叉搜索树到更大和树 - 力扣（LeetCode） 相同

示例 1：

输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

示例 2：

输入：root = [0,null,1]
输出：[1,null,1]

示例 3：

输入：root = [1,0,2]
输出：[3,3,2]

示例 4：

输入：root = [3,2,4,1]
输出：[7,9,4,10]

提示：

• 树中的节点数介于 0 和 104 之间。
• 每个节点的值介于 -104 和 104 之间。
• 树中的所有值 互不相同 。
• 给定的树为二叉搜索树。

代码

class Solution {private int sum = 0; // 全局变量记录累加和public TreeNode convertBST(TreeNode root) {if (root == null) {return null;}// 逆中序遍历（右-根-左）convertBST(root.right); // 先处理右子树（较大值）sum += root.val;        // 更新累加和root.val = sum;         // 当前节点赋值为累加和convertBST(root.left);  // 再处理左子树（较小值）return root;}
}