236. Lowest Common Ancestor of a Binary Tree
题目描述和难度
- 题目描述：
给定一棵二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义： “对于有根树T的两个结点u、v，最近公共祖先表示一个结点x，满足x是u、v的祖先且x的深度尽可能大。”（一个节点也可以是它自己的祖先）
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
_______3______
/ \
___5__ ___1__
/ \ / \
6 _2 0 8
/ \
7 4
示例 1:
输入: root, p = 5, q = 1 输出: 3 解释: 节点5和节点1的最近公共祖先是节点3。
示例 2:
输入: root, p = 5, q = 4 输出: 5 解释: 节点5和节点4的最近公共祖先是节点5。因为根据定义最近公共祖先节点可以为指定节点自身。
- 题目难度：中等。
- 英文网址：236. Lowest Common Ancestor of a Binary Tree 。
- 中文网址：236. 二叉树的最近公共祖先 。
思路分析
求解关键：这道题主要考察了二叉树的后序遍历，先分别从左右子树中递归地找出 p 和 q，如果都能找到，则说明当前结点就是要找的最近公共祖先。
参考解答
参考解答1
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 初始条件：只要等于其中之一，就返回自己，作为后序判断的依据
// 既然是编写递归方法，首先先写出递归终止条件
if (root == null || root == p || root == q) {
return root;
}
// 先在左子树中找，p 和 q 的最近公共祖先
TreeNode left = lowestCommonAncestor(root.left, p, q);
// 再在右子树中找，p 和 q 的最近公共祖先
TreeNode right = lowestCommonAncestor(root.right, p, q);
// 如果左边和右边两者都空，说明，p 和 q 分散在 root 的左右子树中
if (left != null && right != null) {
return root;
}
// 否则返回 left 和 right 中非空的那个
return left == null ? right : left;
}
}
本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0236-lowest-common-ancestor-of-a-binary-tree ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。