标签：right return LeetCode 二叉树 TreeNode 236 root 节点 left

题目

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

思路

自己做只摸到一些门道，还是靠随想录...
代码：

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
	if not root or root == p or root == q:
		return root
	left = self.lowestCommonAncestor(root.left, p, q)
	right = self.lowestCommonAncestor(root.right, p, q)
	if left and right:
		return root
	if left:
		return left
	return right

说明：
一开始我想用全局变量来标记深度最深的祖先节点，但是发现一个问题：无法隔层传递匹配p、q的子节点，遂失败
随想录的思路就是，后序遍历——即从叶子节点往上遍历
如果当前匹配pq 直接return。
这里有一个隐藏事实，pq一定能在左右子树找到！
故，一但找到匹配节点，可以不用管，直接返回
就算该节点下面还有个匹配点，但是此节点已经作为另一节点的祖先了
就算左边只有一个点，那另一个点一定在右子树，故我们必须遍历整棵树

随想录

https://gitee.com/programmercarl/leetcode-master/blob/master/problems/0236.二叉树的最近公共祖先.md#总结

标签：right,return,LeetCode,二叉树,TreeNode,236,root,节点,left
From： https://www.cnblogs.com/Linanjing/p/16847060.html