题解 | #在二叉树中找到两个节点的最近公共祖先#

NC102 在二叉树中找到两个节点的最近公共祖先

描述 给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。

数据范围：1≤n≤1000，树上每个节点的val满足 0<val≤100 要求：空间复杂度 O(1)，时间复杂度 O(n)

注：本题保证二叉树中每个节点的val值均不相同。

思路：二叉树的题就直接递归了（应该有非递归的方法，用while循环，我懒得想）。先找到val为o1或o2的节点。找到了返回T，否则返回F。本来想返回布尔值的，但是我担心如果公共节点的值为0，我写if的时候0会不会当作False，所以就用T和F吧。

如果o1或o2在一个节点的左边则左边结果(leftResult)为T，如果在右边则右边结果(rightResult)为T。最近的公共节点，可能有两种种情况，

1）公共节点的值就为 o1 或 o2，公共节点的左分支或右分支有另一个 o2 或 o1。此时的情况就是公共节点为 T，rightResult 或 leftResult 有一个为 T

2）公共节点的 rightResult 为 T 且 leftResult 也为 T

如果是非公共节点，有三种情况：

1）本节点值为 o1 或 o2，此时返回 T

2）本节点的 rightResult 或 leftResult 为 T，此时返回 T

3）本节点的 rightResult 和 leftResult 都为 F，此时返回 F

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @param o1 int整型 
# @param o2 int整型 
# @return int整型
#
class Solution:
    def lowestCommonAncestor(self , root: TreeNode, o1: int, o2: int) -> int:
        # write code here
        result = ''
        if root == None:
            return 'F'
        elif (root.val == o1) | (root.val == o2):
            result = 'T'
        leftResult = self.lowestCommonAncestor(root.left, o1, o2)
        rightResult = self.lowestCommonAncestor(root.right, o1, o2)
        if result == 'T':
            if (leftResult == 'T') | (rightResult == 'T'):
                return root.val
            else:
                return result
        else:
            if leftResult == 'T':
                if rightResult == 'T':
                    return root.val
                else:
                    return 'T'
            elif leftResult == 'F':
                if rightResult == 'T':
                    return 'T'
                elif rightResult == 'F':
                    return 'F'
                else:
                    return rightResult
            else:
                return leftResult