Problem: 236. 二叉树的最近公共祖先

---

👨‍🏫 参考大佬题解

💖 图解

时间复杂度, 示例： $O(n)$
空间复杂度, 示例： $O(n)$

💖 AC code

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {
//	公共祖先 本先：公共祖先 lca 必然是 p 的祖先 ，也是 q 的祖先/*** @param root 当前树的根* @param p    查找的节点1* @param q    查找的节点2* @return 返回root树中离root节点最近的 p 或 q，返回null则表示无*/public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){
//		找到 p 或 q 了，直接返回 p 或 qif (root == null || root == p || root == q)// 空值，找到头了直接返回return root;
//		左右递归TreeNode left = lowestCommonAncestor(root.left, p, q);TreeNode right = lowestCommonAncestor(root.right, p, q);if (left == null)// 说明当前树root 的左子树无 p或qreturn right;// 则p，q同在右子树，取离root最近的if (right == null)return left;
//	p，q分布在 root的左右子树上，当前 root 即为最近公共祖先（即左子树只有 p或q 一个，那它只能返回p 或 q，右子树同理）return root;}
}