题目描述给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”示例 1输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 1 输出3 树结构 3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4 节点 5 和节点 1 的最近公共祖先是节点 3示例 2输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 4 输出5 节点 5 和节点 4 的最近公共祖先是节点 5 因为节点 5 是节点 4 的祖先且深度最大示例 3输入root [1,2], p 1, q 2 输出1 节点 1 和节点 2 的最近公共祖先是节点 1 一个节点也可以是它自己的祖先提示树中节点数目在范围 [2, 10^5] 内-10^9 Node.val 10^9所有 Node.val 互不相同p ! qp 和 q 均存在于给定的二叉树中解题思路总览方法思路时间复杂度空间复杂度适用场景方法一后序遍历递归后序遍历左右子树查找根据返回判断O(n)O(h)面试首选方法二存储父节点用 HashMap 存储每个节点的父节点然后上浮O(n)O(n)容易理解核心原理如果一个节点既能在左子树找到 p/q又能在右子树找到 p/q那它就是最近公共祖先方法一后序遍历推荐思路利用递归后序遍历的思想从底向上查找如果当前节点为空或者等于 p 或 q直接返回当前节点递归在左子树和右子树中查找 p 和 q根据左右子树的返回结果判断左子树为空说明 p/q 都在右子树返回右子树结果右子树为空说明 p/q 都在左子树返回左子树结果都不为空说明 p/q 分别在左右子树当前节点就是最近公共祖先都为空说明当前子树不包含 p/q返回空完整代码/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */classSolution{public:TreeNode*lowestCommonAncestor(TreeNode*root,TreeNode*p,TreeNode*q){// 递归终止条件节点为空或找到 p 或 qif(rootNULL)returnroot;if(rootp||rootq)returnroot;// 在左右子树中查找TreeNode*leftlowestCommonAncestor(root-left,p,q);TreeNode*rightlowestCommonAncestor(root-right,p,q);// 根据左右子树的返回结果判断if(leftNULL)returnright;// 左子树为空p/q 都在右子树if(rightNULL)returnleft;// 右子树为空p/q 都在左子树returnroot;// 左右都不为空root 是最近公共祖先}};算法流程图以示例 1 为例root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 1树结构 3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4 递归返回过程后序遍历 LCA(node3, p5, q1): nodep? 否, nodeq? 否 left LCA(node5, p5, q1) right LCA(node1, p5, q1) LCA(node5, p5, q1): nodep? 是 → return 5 left 5 LCA(node1, p5, q1): nodeq? 是 → return 1 right 1 left!NULL right!NULL → return node(3) 返回 3逐行解析TreeNode*lowestCommonAncestor(TreeNode*root,TreeNode*p,TreeNode*q){// 递归终止条件节点为空或找到 p 或 qif(rootNULL)returnroot;if(rootp||rootq)returnroot;递归终止条件一root NULL空树直接返回空。递归终止条件二root p || root q找到了 p 或 q返回当前节点。TreeNode*leftlowestCommonAncestor(root-left,p,q);TreeNode*rightlowestCommonAncestor(root-right,p,q);递归在左子树和右子树中查找 p 和 q。使用后序遍历左右根确保从底向上返回结果。if(leftNULL)returnright;左子树为空说明左子树中不存在 p 也不存在 q否则已经返回了。p 和 q 一定都在右子树中返回右子树的结果。if(rightNULL)returnleft;右子树为空说明 p 和 q 都在左子树中。返回左子树的结果。returnroot;左右子树都不为空说明 p 和 q 分别在左右子树中。当前节点就是它们的最近公共祖先。复杂度分析复杂度值说明时间O(n)最坏情况遍历所有节点当 p 和 q 在树的底部时空间O(h)递归栈深度h 为树高优点一次遍历搞定时间效率高代码简洁缺点需要理解后序遍历和递归返回值的设计方法二存储父节点思路第一次 DFS存储每个节点的父节点将 p 的所有祖先节点包括 p 自己加入集合从 q 开始向上浮一直找到第一个出现在集合中的节点完整代码classSolution{public:unordered_mapTreeNode*,TreeNode*parent;voiddfs(TreeNode*node,TreeNode*par){if(!node)return;parent[node]par;dfs(node-left,node);dfs(node-right,node);}TreeNode*lowestCommonAncestor(TreeNode*root,TreeNode*p,TreeNode*q){dfs(root,NULL);// 记录每个节点的父节点unordered_setTreeNode*ancestors;// 将 p 及其所有祖先加入集合while(p){ancestors.insert(p);pparent[p];}// 从 q 开始向上找第一个在集合中的就是 LCAwhile(q){if(ancestors.count(q)){returnq;}qparent[q];}returnNULL;// 不会走到这里}};复杂度分析复杂度值说明时间O(n)两次遍历空间O(n)HashMap 和 HashSet 存储节点两种方法对比维度方法一 后序遍历方法二 存储父节点代码复杂度简洁中等时间复杂度O(n)O(n)空间复杂度O(h)O(n)面试推荐度首选容易想到特点一次遍历搞定需要额外的 parent HashMap面试追问 FAQ问题解答Q1为什么后序遍历能找到最近公共祖先后序遍历的特点是从叶子节点向上返回。递归返回时如果一个节点的左右子树分别包含 p 和 q那该节点就是最近公共祖先因为它既是 p 的祖先也是 q 的祖先且深度最大。Q2为什么 root pQ3如何理解if (left NULL) return right左子树为空有两种情况1左子树不包含 p 也不包含 q2左子树包含了 p 或 q 但没有返回这种情况不存在因为找到就会返回。所以如果左子树为空p 和 q 一定都在右子树中。Q4如果 p 是 q 的祖先结果是什么结果是 p。当递归到节点 p 时root p直接返回 p。然后 p 作为返回值一路向上传递最终成为最终结果。Q5方法二为什么需要 parent HashMap因为方法二是用上浮的方式查找。从 q 开始依次访问父节点直到找到第一个也在 p 的祖先链上的节点。这个父节点关系需要用 HashMap 存储。Q6两种方法如何选择方法一更优因为只需要 O(h) 空间且一次遍历搞定。方法二适合需要频繁查询两个节点的 LCA 的场景可以预处理 parent 信息。相关题目题目难度关键点236. 二叉树的最近公共祖先中等后序遍历LCA235. 二叉搜索树的最近公共祖先简单利用 BST 性质剑指 Offer 68-II. 二叉树的最近公共祖先简单同 2361644. 二叉树中第 K 小的元素中等BST LCA 变形总结要点说明核心原理后序遍历从底向上如果左右子树分别包含 p 和 q当前节点就是 LCA递归终止条件root NULL 或 root p 或 rootq返回值判断left NULL 返回 rightrightNULL 返回 left都不空返回 root时间复杂度O(n)每个节点最多访问一次空间复杂度O(h)递归栈深度