1、题目描述

https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/

相关题：68-1二叉搜索树的最近公共祖先（剑）LeetCode.235 https://blog.csdn.net/IOT_victor/article/details/104622587

2、代码详解

# Definition for a binary tree node. class TreeNode(object): def __init__(self, x): self.val = x self.left = None self.right = None class Solution(object): def lowestCommonAncestor(self, root, p, q): """ :type root: TreeNode :type p: TreeNode :type q: TreeNode :rtype: TreeNode """ if not root or root == p or root == q: return root # 通过递归对二叉树进行 后序遍历，当遇到节点 p 或 q 时返回。 # 从底至顶回溯，当节点 p, q 在节点 root 的异侧时，节点 root 即为最近公共祖先，则向上返回 root 。 left = self.lowestCommonAncestor(root.left, p, q) right = self.lowestCommonAncestor(root.right, p, q) if not left and not right: return # 1.说明 root 的左 / 右子树中都不包含 p,q，返回 null if not left: # 3.p,q 都不在 root 的左子树中，直接返回 right，具体可分为两种情况： # p,q 其中一个在 root 的 右子树 中，此时 right 指向 p（假设为 p ） # p,q 两节点都在 root 的 右子树 中，此时的 right 指向 最近公共祖先节点 return right if not right: return left # 4.同理3 return root # 2. if left and right: 同时不为空 ：说明 p, q 分列在 root 的 异侧 （分别在 左 / 右子树），因此 root 为最近公共祖先，返回 root

https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/236-er-cha-shu-de-zui-jin-gong-gong-zu-xian-hou-xu/