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

# 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 , o1 , o2 ):
        # write code here
        stack = {}
        maxLevel = 0

        visitedN = []
        sig = 1
        visitedN.append([1,root,sig])
        while len(visitedN)>0:
            node = visitedN.pop()
            if maxLevel < node[0]:
                maxLevel = node[0]
            elif maxLevel > node[0]:
                del stack[maxLevel]
                maxLevel = maxLevel - 1
            stack[node[0]]= [node[1],sig]
            if node[1].val == o1 or node[1].val == o2:
                if sig==0:
                    break
                sig = 0
            if node[1].right is not None:
                visitedN.append([node[0]+1, node[1].right,sig])
            if node[1].left is not None:
                visitedN.append([node[0]+1,node[1].left,sig])
        while stack[maxLevel][1]==0:
                maxLevel-=1              
        return stack[maxLevel][0].val