力扣日刷47-补

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

这一题的逻辑说句实话也是非常地难懂。下面我来做一个总结吧：

首先，我们的边界条件是，如果节点为空或者节点是pq其中一个返回节点的值。

然后我们进行后序的遍历。这个遍历相当于是去刨根问底一定要找到p或者q或者所有的节点。因为我们设置了返回条件，所以只有当确实到底了或者找到结点的时候才能返回，然后我们便是要去判断是不是公共祖先，当左边返回来有值，右边也返回来有值的时候这个节点就是我们要的最近祖先，如果左边有值，右边没值的话，返回左边的节点。如果右边有值，返回右边的节点。

# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': if root is None or root is p or root is 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

235.二叉搜索树的最近公共祖先

这一道题是这样的，跟上一题差不多这一题，会更简单一点，这一题用到的是更加简易的判断。返回递归条件设置为了当两个值都在一侧的时候进入迭代，在哪一侧就进入哪一侧。然后直到p跟q的值在当前节点的两边。此时的节点就是我们需要的节点

# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': x = root.val if p.val <x and q.val<x: return self.lowestCommonAncestor(root.left,p,q) if p.val > x and q.val > x: return self.lowestCommonAncestor(root.right,p,q) return root