废话不多说，喊一句号子鼓励自己：程序员永不失业，程序员走向架构！本篇Blog的主题是【二叉树的节点查找】，使用【二叉树】这个基本的数据结构来实现，这个高频题的站点是：CodeTop，筛选条件为：目标公司+最近一年+出现频率排序，由高到低的去牛客TOP101去找，只有两个地方都出现过才做这道题（CodeTop本身汇聚了LeetCode的来源），确保刷的题都是高频要面试考的题。
明确目标题后，附上题目链接，后期可以依据解题思路反复快速练习，题目按照题干的基本数据结构分类，且每个分类的第一篇必定是对基础数据结构的介绍。
二叉搜索树的最近公共祖先【MID】
同上一题的解法，再练习一遍
题干
解题思路
根据以上定义，若 root 是 p,q的 最近公共祖先 ，则只可能为以下情况之一：
- p 和 q 在 root 的子树中，且分列 root 的 异侧（即分别在左、右子树中）；
- p=root ，且 q 在 roo的左或右子树中；
- q=root，且 p 在 root的左或右子树中；
- 终止条件：当越过叶节点，则直接返回 null；当 root 等于 p,q，则直接返回 root；
- 递推工作： 开启递归左子节点，返回值记为 left；开启递归右子节点，返回值记为 right；
- 返回值： 根据 left和 right，可展开为四种情况；
- 当 left 和 righ同时为空 ：说明一直遍历到叶节点， root 的左 / 右子树中都不包含 p,q ，返回 null；
- 当 left和 right 同时不为空 ：说明 pq 分列在 roo的 异侧 （分别在 左 / 右子树），因此 root为最近公共祖先，返回 root
- 当 left为空 ，right不为空 ：pq 都不在 root 的左子树中，直接返回 right。具体可分为两种情况：pq 其中一个在 root 的 右子树 中，此时 right指向 p（假设为 p ）；pq 两节点都在 root的 右子树 中，此时的 right指向 最近公共祖先节点 ；
- 当 left不为空 ， right为空 ：与情况 3. 同理
代码实现
给出代码实现基本档案
基本数据结构：二叉树
辅助数据结构：无
算法：递归、DFS
技巧：无
其中数据结构、算法和技巧分别来自：
- 10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
- 10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
- 技巧：双指针、滑动窗口、中心扩散
当然包括但不限于以上
public TreeNode lowestCommonAncestor (TreeNode root, TreeNode p, TreeNode q) { if (root == null) { return null; } return dfsFindRoot(root, p, q); } private TreeNode dfsFindRoot(TreeNode node, TreeNode p, TreeNode q) { // 1 递归终止条件：越过叶子节点没找到;root为p或root为q if (node == null || node == p || node == q) { return node; } // 2 本级任务：分别在左右子树中寻找节点 TreeNode left = dfsFindRoot(node.left, p, q); TreeNode right = dfsFindRoot(node.right, p, q); // 3 本级任务：分别在左右子树中寻找节点 if (left != null && right != null) { //如果两个节点分别存在于左右子树，则当前节点即是最近公共祖先 return node; } // 如果两个节点在root的同侧,则返回的节点即为公共节点 if (right == null && left != null) { return left; } if (right != null && left == null) { return right; } // 如果两个节点左右都没有找到,则返回null return null; }
复杂度分析
时间复杂度：O(n)，其中n为二叉树的节点数，遍历整棵二叉树
空间复杂度：O(n)，最坏情况下，二叉树化为链表，递归栈深度最大为n
二叉树的最近公共祖先【MID】
最近公共祖先（Lowest Common Ancestor, LCA）是指在一个二叉树中，两个节点p和q的最低公共祖先节点，即深度最深且同时是p和q的祖先的节点，同时节点本身也可以为其最近公共祖先
题干
解题思路
根据以上定义，若 root 是 p,q的 最近公共祖先 ，则只可能为以下情况之一：
- p 和 q 在 root 的子树中，且分列 root 的 异侧（即分别在左、右子树中）；
- p=root ，且 q 在 roo的左或右子树中；
- q=root，且 p 在 root的左或右子树中；
- 终止条件：当越过叶节点，则直接返回 null；当 root 等于 p,q，则直接返回 root；
- 递推工作： 开启递归左子节点，返回值记为 left；开启递归右子节点，返回值记为 right；
- 返回值： 根据 left和 right，可展开为四种情况；
- 当 left 和 righ同时为空 ：说明一直遍历到叶节点， root 的左 / 右子树中都不包含 p,q ，返回 null；
- 当 left和 right 同时不为空 ：说明 pq 分列在 roo的 异侧 （分别在 左 / 右子树），因此 root为最近公共祖先，返回 root
- 当 left为空 ，right不为空 ：pq 都不在 root 的左子树中，直接返回 right。具体可分为两种情况：pq 其中一个在 root 的 右子树 中，此时 right指向 p（假设为 p ）；pq 两节点都在 root的 右子树 中，此时的 right指向 最近公共祖先节点 ；
- 当 left不为空 ， right为空 ：与情况 3. 同理
代码实现
给出代码实现基本档案
基本数据结构：二叉树
辅助数据结构：无
算法：递归、DFS
技巧：无
其中数据结构、算法和技巧分别来自：
- 10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
- 10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
- 技巧：双指针、滑动窗口、中心扩散
当然包括但不限于以上
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param root TreeNode类 * @param p int整型 * @param q int整型 * @return int整型 */ public int lowestCommonAncestor (TreeNode root, int p, int q) { if (root == null) { return -1; } return dfsCheck(root, p, q); } private int dfsCheck(TreeNode node, int p, int q) { // 1 递归终止条件，找到了则返回值，超过叶子节点没找到则返回-1 if (node == null) { return -1; } if ( node.val == p || node.val == q) { return node.val; } // 2 获取左右子树的查找结果 int rightVal = dfsCheck(node.right, p, q); int leftVal = dfsCheck(node.left, p, q); // 3 依据查找结果判断取值 if (rightVal != -1 && leftVal != -1) { // p、q分别在左右子树，且都不作为公共祖先 return node.val; } else if (rightVal == -1) { // 右子树没有找到，左子树找到了，则返回左子树找到的最近公共祖先 return leftVal; } else if (leftVal == -1) { // 左子树没有找到，右子树找到了，则返回右子树找到的最近公共祖先 return rightVal; } else { // 两边都没找到，返回-1； return -1; } } }
复杂度分析
时间复杂度：O(n)，其中n为二叉树的节点数，遍历整棵二叉树
空间复杂度：O(n)，最坏情况下，二叉树化为链表，递归栈深度最大为n
拓展知识：二叉树的最近公共祖先
最近公共祖先（Lowest Common Ancestor, LCA）是指在一个二叉树中，两个节点p和q的最低公共祖先节点，即深度最深且同时是p和q的祖先的节点。以下是一种基于递归的实现思路，并提供Java的实现代码：
定义
假设有一个二叉树，每个节点包含如下信息：
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int val) { this.val = val; this.left = null; this.right = null; } }
实现思路
- 从根节点开始遍历二叉树。
- 对于当前节点，递归地查找其左子树和右子树，看看是否能找到节点p和节点q。
- 如果左子树中找到了节点p或节点q，或者右子树中找到了节点p或节点q，那么当前节点就是它们的最近公共祖先。
- 如果左子树和右子树都找到了最近公共祖先，那么当前节点就是它们的最近公共祖先。
- 最后，返回最近公共祖先。
Java实现代码
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { // Base case: 如果当前节点为空或者等于p或q中的任意一个，直接返回当前节点 if (root == null || root == p || root == q) { return root; } // 递归查找左子树和右子树 TreeNode leftLCA = lowestCommonAncestor(root.left, p, q); TreeNode rightLCA = lowestCommonAncestor(root.right, p, q); // 如果左子树和右子树都找到了最近公共祖先，那么当前节点就是最近公共祖先 if (leftLCA != null && rightLCA != null) { return root; } // 如果只在一侧找到了最近公共祖先，返回那一侧找到的结果 return (leftLCA != null) ? leftLCA : rightLCA; }
这段代码会在二叉树中查找节点p和q的最近公共祖先，并返回该节点。如果一个节点是另一个节点的祖先，那么它自己也可以是自己的祖先，因此在递归中会检查当前节点是否等于p或q中的任意一个，如果是就返回当前节点。否则，递归地查找左子树和右子树，并根据左右子树的结果确定最近公共祖先。
