Leetcode 腾讯50题 day15

No.231 2的幂

题目描述

给定一个整数，编写一个函数来判断它是否是 2 的幂次方。

输入: 1
输出: true
解释: 20 = 1

代码

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n&(n-1)==0 if n>0 else False

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

题目描述

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

代码

# 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':
        l = []
        def preorder(root):
            if root:
               l.append(root)
               preorder(root.left)
               preorder(root.right)

        preorder(root)
        a = min(p.val, q.val)
        b = max(p.val, q.val)
        for x in l:
            if a <= x.val <= b:
                return x

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

题目描述

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

代码

# 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':
        res = []
        def searchpq(root):
            if not root or len(res)!=0:
                return False
            flag1 = searchpq(root.left)
            flag2 = searchpq(root.right)
            flag3 = (p==root or q==root)
            # print(f'1,2,3,val:{flag1}, {flag2}, {flag3}, {root.val}')
            if (flag3 and flag1) or (flag3 and flag2) or (flag1 and flag2):
                res.append(root)
                return False
            return flag1 or flag2 or flag3


        searchpq(root)
        return res[0]