代码随想录-Day22

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

方法一：两次遍历

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {List<TreeNode> path_p = getPath(root, p);List<TreeNode> path_q = getPath(root, q);TreeNode ancestor = null;for (int i = 0; i < path_p.size() && i < path_q.size(); ++i) {if (path_p.get(i) == path_q.get(i)) {ancestor = path_p.get(i);} else {break;}}return ancestor;}public List<TreeNode> getPath(TreeNode root, TreeNode target) {List<TreeNode> path = new ArrayList<TreeNode>();TreeNode node = root;while (node != target) {path.add(node);if (target.val < node.val) {node = node.left;} else {node = node.right;}}path.add(node);return path;}
}

这段代码定义了一个名为 Solution 的类，用于求解二叉搜索树（Binary Search Tree, BST）中两个指定节点的最近公共祖先（Lowest Common Ancestor, LCA）。类中包含两个方法：

1. lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)：

   • 功能：该方法接收BST的根节点 root 和需要寻找LCA的两个节点 p 和 q 作为参数，返回这两个节点的最近公共祖先。
   • 实现：首先，分别调用 getPath 方法获取节点 p 和 q 到根节点的路径（以节点列表形式存储）。然后，遍历这两个路径，找到路径中最后一个相同的节点，即为最近公共祖先。如果两个路径没有共同节点（理论上在BST中不会发生，除非 p 或 q 不在树中），则返回 null（虽然代码中未直接处理这种情况，但循环结束时 ancestor 仍为 null）。

2. getPath(TreeNode root, TreeNode target)：

   • 功能：该方法接收BST的根节点 root 和目标节点 target，返回从根到目标节点的路径上的所有节点列表。
   • 实现：通过一个循环不断比较当前节点与目标节点的值，决定是向左子树还是右子树移动。同时，将访问过的节点按路径顺序添加到列表 path 中。当找到目标节点时，将目标节点也添加到路径列表，并返回整个路径。

注意，这段代码的高效运行依赖于输入是二叉搜索树的特性，即树中任意节点的左子树所有节点的值都小于该节点的值，右子树所有节点的值都大于该节点的值。这使得在寻找特定值的节点时，可以快速地在树中进行定向移动，而不需要回溯，因此每个 getPath 方法的时间复杂度为O(log n)，其中n是树中的节点数。整体的 lowestCommonAncestor 方法的时间复杂度也是O(log n)，因为两个路径的最长公共前缀长度不会超过树的高度。

方法二：一次遍历

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {TreeNode ancestor = root;while (true) {if (p.val < ancestor.val && q.val < ancestor.val) {ancestor = ancestor.left;} else if (p.val > ancestor.val && q.val > ancestor.val) {ancestor = ancestor.right;} else {break;}}return ancestor;}
}

这段代码定义了一个名为 Solution 的类，其中包含一个方法 lowestCommonAncestor，用于在给定的二叉搜索树（BST）中找到两个指定节点 p 和 q 的最近公共祖先（LCA）。这个方法直接利用了BST的性质（即左子树所有节点的值小于根节点值，右子树所有节点的值大于根节点值），以迭代而非递归的方式高效地解决了问题。以下是代码的详细解释：

• 方法签名：public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) 接受三个参数，分别是BST的根节点 root，以及需要找LCA的两个节点 p 和 q。

• 初始化祖先节点：首先将 ancestor 初始化为根节点 root。

• 循环查找：进入一个 while 循环，循环条件默认为 true，意味着它将一直执行，直到通过 break 语句跳出循环。

  • 在循环内，首先检查 p 和 q 的值与当前 ancestor 节点值的关系：
    • 如果 p 和 q 的值都小于 ancestor 的值，说明它们都在当前节点的左子树中，因此将 ancestor 更新为其左子节点。
    • 如果 p 和 q 的值都大于 ancestor 的值，说明它们都在当前节点的右子树中，因此将 ancestor 更新为其右子节点。
    • 如果以上两种情况都不满足，说明当前 ancestor 节点满足以下至少一种情况：
      • 它正好是 p 或 q 中的一个。
      • 它位于 p 和 q 之间，即一个在它的左子树，另一个在它的右子树，或者两者都在同一边但当前节点就是最近的共同祖先。
    • 在这种情况下，通过 break 退出循环，因为已经找到了最近公共祖先。

• 返回结果：循环结束后，ancestor 节点即为所求的最近公共祖先，直接返回该节点。

这种方法的时间复杂度为 O(h)，其中 h 是树的高度，因为在最坏情况下，我们可能需要从根节点一直走到 p 或 q 中较深的那个节点。由于是二叉搜索树，高度 h 最坏情况下为 n（树退化为链表的情况），最好情况下为 log(n)。空间复杂度为 O(1)，因为我们只使用了固定数量的指针变量，没有使用额外的空间来存储节点路径等。

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

class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {if (root == null) {return new TreeNode(val);}TreeNode pos = root;while (pos != null) {if (val < pos.val) {if (pos.left == null) {pos.left = new TreeNode(val);break;} else {pos = pos.left;}} else {if (pos.right == null) {pos.right = new TreeNode(val);break;} else {pos = pos.right;}}}return root;}
}

这段代码定义了一个名为 Solution 的类，其中包含一个方法 insertIntoBST，该方法用于将一个值插入到给定的二叉搜索树（Binary Search Tree, BST）中。二叉搜索树的特性是：对于任意一个节点，其左子树中的所有节点的值都小于该节点的值，其右子树中的所有节点的值都大于该节点的值。以下是方法的逻辑解析：

• 方法签名：public TreeNode insertIntoBST(TreeNode root, int val) 接受两个参数，一个是BST的根节点 root，另一个是要插入的值 val。

• 基本情况处理：首先检查 root 是否为空。如果为空，说明当前树为空，那么直接创建一个新的 TreeNode，其值为 val，并返回这个新节点作为新树的根。

• 寻找插入位置：如果根节点不为空，声明一个指针 pos 指向当前考虑的节点（初始化为根节点 root），然后进入一个 while 循环，用于找到插入新节点的位置。

  • 在循环中，如果 val 小于 pos 节点的值，则向左子树移动；如果 val 大于或等于 pos 节点的值，则向右子树移动。每次移动时，如果遇到空的子节点（即找到了插入位置），则在相应位置创建一个新节点，值为 val，并跳出循环。

• 返回结果：循环结束后，无论是否插入新节点，根节点 root 的引用都保持不变，直接返回 root 即可。因为插入操作是在原有的树结构基础上进行的，没有改变根节点本身，只是在其某个子树上新增了节点。

这种方法保持了二叉搜索树的性质，插入操作的时间复杂度在最坏情况下为 O(H)，其中 H 是树的高度。对于平衡的二叉搜索树，平均情况下插入操作的时间复杂度为 O(log N)，N 为树中节点的数量。

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

方法一：递归

class Solution {public TreeNode deleteNode(TreeNode root, int key) {if (root == null) {return null;}if (root.val > key) {root.left = deleteNode(root.left, key);return root;}if (root.val < key) {root.right = deleteNode(root.right, key);return root;}if (root.val == key) {if (root.left == null && root.right == null) {return null;}if (root.right == null) {return root.left;}if (root.left == null) {return root.right;}TreeNode successor = root.right;while (successor.left != null) {successor = successor.left;}root.right = deleteNode(root.right, successor.val);successor.right = root.right;successor.left = root.left;return successor;}return root;}
}

这段代码定义了一个名为 Solution 的类，其中包含一个方法 deleteNode，用于在给定的二叉搜索树（BST）中删除具有给定值的节点。二叉搜索树的特性是左子树中的所有节点的值小于当前节点值，右子树中的所有节点的值大于当前节点值。下面是代码逻辑的详细解析：

1. 基本情况处理：首先检查根节点是否为空，如果为空，则直接返回 null，表示树为空或目标节点不存在。

2. 查找目标节点：利用BST的性质进行查找。如果目标值 key 小于当前节点值 root.val，则在左子树中递归删除；如果 key 大于当前节点值，则在右子树中递归删除。这一步骤会一直进行到找到目标节点或递归到空节点为止。

3. 删除目标节点：

   • 当找到目标节点（即 root.val == key）时，有三种情况：
     • 叶子节点：如果目标节点没有左右子节点，直接返回 null，让其父节点指向 null 达到删除效果。
     • 仅有一个子节点：如果目标节点只有左子节点或右子节点，直接返回其非空的子节点，使父节点指向这个子节点。
     • 有两个子节点：找到目标节点的后继节点（即右子树中的最小节点 successor），用后继节点替换当前目标节点。然后在右子树中递归删除这个后继节点（因为后继节点可能是其所在子树的最小值，也可能有右子节点，故需要递归删除以保持BST性质）。后继节点的左子树挂载到原目标节点的左子树上，原目标节点的右子树挂载到后继节点的右子树上，这样既删除了目标节点，又保持了BST的结构。

4. 返回处理结果：在递归的每一步中，直接返回处理后的子树根节点，这样可以保证上一层递归能够正确接收到更新后的子树状态。

通过上述逻辑，该方法能够有效地在二叉搜索树中删除指定值的节点，同时保持树的二叉搜索特性。