题解 | #判断是不是平衡二叉树#

这道题说是用递归/搜索与回溯，但是我的想法是用暴力求解，先在init中定义一个数据结构val_set，紧接着将以某个节点为根节点的树中的节点值加入到val_set中，使用函数isAncestor判断根节点是否为祖先，最后使用层序遍历，找到最近的根节点。 缺点是时间复杂度太高

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @param p int整型 
# @param q int整型 
# @return int整型
#
class Solution:
    def __init__(self):
        self.val_set = set()
        
    def rootval(self, root):
        if root.left:
            self.rootval(root.left)
        self.val_set.add(root.val)
        if root.right:
            self.rootval(root.right)
        
        return self.val_set
    
    def isAncestor(self,root,p,q):
        if p in self.rootval(root) and q in self.rootval(root):
            print(self.rootval(root))  
            return True
        else:
            return False
    
    def lowestCommonAncestor(self , root: TreeNode, p: int, q: int) -> int:
        # write code here
        # 第一种方法：记录以某个节点为根节点的树，他的节点值中是否有目标值
        res = -1
        node = list()
        node.append(root)
        while node:
            temp = list()
            while node:
                node_temp = node.pop()
                if self.isAncestor(node_temp,p,q):
                    res = node_temp.val
                self.val_set.clear()
                if node_temp.left:
                    temp.append(node_temp.left)
                if node_temp.right:
                    temp.append(node_temp.right)
            node = temp
        
        return res