578 · 最近公共祖先 III - LintCode

Difficulty
Medium
Tags
二叉树
URL
https://www.lintcode.com/problem/578
Star
描述
给一棵二叉树和二叉树中的两个节点，找到这两个节点的最近公共祖先LCA。
两个节点的最近公共祖先，是指两个节点的所有父亲节点中（包括这两个节点），离这两个节点最近的公共的节点。
返回 null 如果两个节点在这棵树上不存在最近公共祖先的话。
样例
样例1
输入:
{4, 3, 7, #, #, 5, 6}
3 5
5 6
6 7
5 8
输出:
4
7
7
null
解释:
  4
 / \
3   7
   / \
  5   6

LCA(3, 5) = 4
LCA(5, 6) = 7
LCA(6, 7) = 7
LCA(5, 8) = null
样例2
输入:
{1}
1 1
输出:
1
说明：
这棵树只有一个值为1的节点

法 1 自下而上

参考
🎱
236. 二叉树的最近公共祖先 但本题目的两个节点 不一定在 二叉树中，所以需要完整的找到两个节点，然后 count += 1，最后再判断 count == 2。
在236中，我们只要找到一个节点是p或者q就不再继续往下遍历了。因为没必要了，但本题目还要继续往下走，因为最后要判断 count == 2 ？
要求完整的找到两个节点，所以不能找到一个节点就返回，而应该继续往下遍历。
或者转化一下思路，先遍历完整，再找节点。
题解
class Solution:
    """
    @param: root: The root of the binary tree.
    @param: A: A TreeNode
    @param: B: A TreeNode
    @return: Return the LCA of the two nodes.
    """
    def lowestCommonAncestor3(self, root, A, B):
        # write your code here
        self.count = 0
        res = self.helper(root, A, B)
        if self.count == 2:
            return res
        return None

    def helper(self, root, p, q):
        if root is None:
            return None
        
        l = self.helper(root.left, p, q)
        r = self.helper(root.right, p, q)
				# 遍历到底 再判断
        if root is q or root is p:
            self.count += 1
            return root
        
        if l is None and r is None:
            return None
        elif l is None or r is None:
            return l if l else r
        else:
            return root