前言
祖先的定义： 若节点 p 在节点 root 的左（右）子树中，或 p = root，则称 root 是 p 的祖先。
最近公共祖先的定义： 设节点 root 为节点 p,q 的某公共祖先，若其左子节点 root.left 和右子节点 root.right 都不是 p,q 的公共祖先，则称 root 是 “最近的公共祖先” 。
根据以上定义，若 root 是 p,q 的 最近公共祖先 ，则只可能为以下情况之一：
- p 和 q 在 root 的子树中，且分列 root 的 异侧（即分别在左、右子树中）；
- p=root ，且 q 在 root 的左或右子树中；
- q=root ，且 p 在 root 的左或右子树中；
网络异常，图片无法展示
|
Leetcode-235. 二叉搜索树的最近公共祖先
分析
先来回顾下二叉搜索树的相关性质：
二叉搜索树按照中序遍历是有序的，左孩子所有结点的值都小于根结点，右孩子所有结点的值大于根结点
本题使用递归的方法：
- 如果p，q的值均小于根结点，则在左孩子中找公共祖先
- 如果p，q的值均大于根结点，则在右孩子中找公共祖先
- 否则，返回根结点，包含三种情况（1）p=root (2) q=root (3) p,q在root的两侧。
代码实现（Javascript版）
var lowestCommonAncestor = function(root, p, q) { if(p.val < root.val && q.val < root.val){ return lowestCommonAncestor(root.left, p, q); } if(p.val > root.val && q.val > root.val){ return lowestCommonAncestor(root.right, p, q); } return root }; 复制代码
Leetcode-236. 二叉树的最近公共祖先
分析
对于二叉树的两个节点node1和node2，找到他们的最低公共祖先节点，会有两种情况：
- node1是node2的最低公共祖先，或node2是node1的最低公共祖先
- node1与node2不互为最低公共祖先（不在一个子树上，需要通过向上汇聚才能找到最低公共祖先）
思路
二叉树没有二叉搜索树的性质，这里依然使用递归解决，通过递归对二叉树进行先序遍历，当遇到节点 node1 或 node2时返回。从底至顶回溯，当节点 node1,node2 在节点 root 的异侧时，节点 root 即为最近公共祖先，则向上返回 root。
lowestAncestor函数实现了：
- 若node1、node2其中之一等于根结点root，则返回node1,node2 （找到node1或node2，此时返回的不一定是最近公共祖先，有可能另一个结点找不到）
- 否则，返回最近公共祖先
递归解析
终止条件：
- 当遍历到叶节点，则直接返回null
- 当root等于node1、node2，则直接返回root递推工作：
- 开启递归左子节点，返回值记为left
- 开启递归右子节点，返回值记为right
分析返回值：
根据left和right，可展开为四种情况：
- 当left和right同时为空，说明root的左/右子树都不包含node1、node2，返回null
- 当left和right同时不为空，说明node1、node2分列在root的异侧（分别在左/右子树），因此root为最近公共祖先，返回root
- 当left为空，right不为空，node1、node2都不在root的左子树中，直接返回right。此处一般有两种情况：
- 1）node1、node2其中一个在root的右子树中，此时right指向node1（假设为node1）
- 2）node1、node2两节点都在root的右子树中，此时的right指向最近公共祖先节点
- 当left不为空，right为空，与情况3雷同
代码实现
Java版
// 易理解版 public static Node lowestAncestor(Node head, Node o1, Node o2){ if(head == null || head == o1 || head == o2){ return head; } Node left = lowestAncestor(head.left, o1, o2); Node right = lowestAncestor(head.right, o1, o2); if(left == null && right == null) return null; // 1. if(left == null) return right; // 3. if(right == null) return left; // 4. return root; // 情况2. 相当于if(left != null and right != null) } // 进一步简写 public static Node lowestAncestor(Node head, Node o1, Node o2){ if(head == null || head == o1 || head == o2){ return head; } Node left = lowestAncestor(head.left, o1, o2); Node right = lowestAncestor(head.right, o1, o2); // 不可能左边和右边都找到了公共祖先，只可能是左边和右边分别找到了o1、o2，返回根节点 if(left != null && right != null){ return head; } // 左边找不到o1或o2或公共祖先，o1、o2都在右孩子； // 右边找不到o1或o2或公共祖先，o1、o2都在左孩子； return left != null ? left : right; } 复制代码
Javascript版
var lowestCommonAncestor = function(root, p, q) { if(root == p || root == q || !root) return root; let left = lowestCommonAncestor(root.left, p, q); let right = lowestCommonAncestor(root.right, p, q); if(!left && !right) return null; if(left && right){ return root } return left || right; };
