【算法训练营Day17】二叉树part7

二叉树的最近公共祖先

题目链接：236. 二叉树的最近公共祖先

解题逻辑：

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

我们想要寻找两个节点的最近公共祖先，是一个从下向上寻找的过程，那么我们可以通过递归中的归来解决（向下递，向上归）。

我们可以通过两种思路来解决这个问题：

• 递归的返回值的传递
• 回溯算法

这两种思路都可以实现从下到上的逻辑处理。

这里我们使用递归返回值这种方法。

从递归三要素来考虑，本题采用后序遍历：

• 递归参数与返回值：递归的参数就是根节点、以及两个树节点。而递归的返回值是可以层层向上传递的，我们可以设置为set，代表当前节点的左右子树中包含p、q中的哪个节点。
• 递归的出口：当node为null的时候，返回空set即可
• 递归逻辑：
  • 获得左、右节点所具有的孩子节点
  • 创建一个新set
  • 如果当前节点是p、q中的一个则将当前节点放入set
  • 将当前set与左右节点返回的set合并
  • 如果合并之后set中同时包含p、q则说明该节点为最近的公共祖先，将其赋值给类字段
  • 否则返回set

代码如下：

class Solution {TreeNode result = null;boolean first = true;public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {findTree(root,p.val,q.val);return result;}public Set<Integer> findTree(TreeNode node,Integer p,Integer q){if(node == null) return new HashSet<Integer>();Set<Integer> left =  findTree(node.left,p,q);Set<Integer> right =  findTree(node.right,p,q);Set<Integer> set = new HashSet<>();if(node.val == p) set.add(p);else if(node.val == q) set.add(q);set.addAll(left);set.addAll(right);if(set.contains(p) && set.contains(q) && first) {result = node;first = false;}return set;}
}

上面这种算法的核心逻辑就是：只要该节点的左右子树中包含p、q中的任意一个就向上传递，当某一节点凑齐p、q那么就说明该节点是p、q最近的公共祖先。

当然上面的算法效率并不高，我们可以根据题意简洁一下算法，将递归的返回值换为boolean，只要子树中包含p或者q就返回true，代码如下：

class Solution {TreeNode result = null;public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {findTree(root,p.val,q.val);return result;}public boolean findTree(TreeNode node,Integer p,Integer q){if(node == null) return false;boolean left =  findTree(node.left,p,q);boolean right =  findTree(node.right,p,q);if(left && right) {result = node;return true;}else if(node.val == p && (left || right)) {result = node;return true;}else if(node.val == q && (left || right)){result = node;return true;}else if(node.val == q || node.val == p) {return true;}return left || right;}
}

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

题目链接：235. 二叉搜索树的最近公共祖先

解题逻辑：

这个题可以直接使用上面的代码，但是效率很低，因为没有使用到二叉搜索树的特性。

在二叉搜索树中要想找到两个节点p、q的最近公共祖先，我们可以从上往下遍历。

• 如果当前节点数值小于p、q两个节点，那么说明p、q均在该节点的右子树中，继续往右子树中搜索
• 如果当前节点数值大于p、q两个节点，那么说明p、q均在该节点的左子树中，继续往左子树中搜索
• 如果当前节点的数值在p、q两个节点之间，那么就说明该节点就为p、q的最近公共节点（此时p、q肯定分别在该节点的左右子树上，不会有更近的，因为如果继续深入寻找，进入任意一边的子树都将失去另一边子树的节点）

代码如下：

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null) return null;TreeNode left = null;TreeNode right = null;if(root.val > Math.max(p.val,q.val)) left = lowestCommonAncestor(root.left,p,q);else if(root.val < Math.min(p.val,q.val)) right = lowestCommonAncestor(root.right,p,q);else if(root.val >= Math.min(p.val,q.val) && root.val <= Math.max(p.val,q.val)) return root;if(left != null) return left;else if(right != null) return right;return null;}
}

二叉搜索树中的插入操作

题目链接：701. 二叉搜索树中的插入操作

解题逻辑：
若二叉搜索树为空，则直接插入节点。否则若val小于跟节点值，则插入到左子树。相反则插入到右子树。

代码如下：

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

删除二叉搜索树中的节点

题目链接： 450. 删除二叉搜索树中的节点

删除二叉树中的节点分为三种情况：

• 若被删除节点是叶子节点，则直接删除
• 若被删除节点只有一棵子树，则直接让其子树替代位置即可
• 若被删除节点有两颗子树，则让被删除节点的直接后继（或者直接前驱）替代被删除节点，然后从二叉搜索树中删除这个直接后继（或者直接前驱），这样就转换成了前面两种情况

代码如下：

class Solution {int preNum = Integer.MAX_VALUE;public TreeNode deleteNode(TreeNode root, int key) {if(root == null) return null;TreeNode left = deleteNode(root.left,key);if(root.val == key) {if(root.left == null && root.right == null) return null;else if(root.left != null && root.right == null) return root.left;else if(root.left == null && root.right != null) return root.right;else if(root.left != null && root.right != null) {int rem = preNum;TreeNode node = deleteNode(root,rem);node.val = rem;preNum = rem;return node;}}preNum = root.val;TreeNode right = deleteNode(root.right,key);root.left = left;root.right = right;return root;}
}