0

LeetCode 腾讯精选练习50题 - 231, 235, 236

 5 months ago
source link: https://jianengli.github.io/2021/01/27/leetcode/tenxun_jingxuan/tx15/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Jianeng

LeetCode 腾讯精选练习50题 - 231, 235, 236

Created2021-01-27|Updated2021-01-28|LeetCode 腾讯精选练习50题
Word count:936|Reading time:3min|Post View:16

今天我们一起掌握 leetocode 的 231, 235, 236 题。

1. lc 231 - 2的幂

  • 题目来源
  • 给定一个整数,编写一个函数来判断它是否是 2 的幂次方。
  • 难度:简单

1.1 解题思路 - 位运算

没看过这个解法,我就想不到,上图吧。

python
class Solution(object):
def isPowerOfTwo(self, n):
"""
:type n: int
:rtype: bool
"""
return n > 0 and n & n - 1 == 0

2. lc 235 - 二叉搜索树的最近公共祖先

  • 题目来源
  • 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
  • 难度:简单

2.1 解题思路 - 迭代

二叉搜索树的特点就是 左子树的所有节点都小于当前节点,右子树的所有节点都大于当前节点,并且每棵子树都具有上述特点。

对于一个节点root,有三种情况:

  • 如果两个节点值都小于根节点,说明他们都在根节点的左子树上,我们往左子树上找
  • 如果两个节点值都大于根节点,说明他们都在根节点的右子树上,我们往右子树上找
  • 如果一个节点值大于根节点,一个节点值小于根节点,说明他们他们一个在根节点的左子树上一个在根节点的右子树上,那么根节点就是他们的最近公共祖先节点。

时间复杂度

  • 时间复杂度: O(n)。在最坏的情况下,树呈现链式结构。
  • 空间复杂度: O(1)。
python
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
while True:
if root.val<p.val and root.val<q.val:
root = root.right
elif root.val>p.val and root.val>q.val:
root = root.left
else:
return root

2.2 解题思路 - 递归

与2.1一致的思路,递归写法。

时间复杂度

  • 时间复杂度: O(n)。
  • 空间复杂度: O(n)。递归深度达到 N ,系统使用 O(N) 大小的额外空间。
python
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
if root.val>p.val and root.val>q.val:
return self.lowestCommonAncestor(root.left,p,q)
elif root.val<p.val and root.val<q.val:
return self.lowestCommonAncestor(root.right,p,q)
return root

3. lc 236 - 二叉树的最近公共祖先

3.1 解题思路 - 递归

直接看 高赞解析 吧,很本质。

3.2 复杂度分析

  • 时间复杂度:O(n)。最差情况下,需要递归遍历树的所有节点。
  • 空间复杂度:O(n)。最差情况下,递归深度达到 N ,系统使用 O(N) 大小的额外空间。

3.3 代码

python
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
if not root: return root
if p is root or q is root: return root
left = self.lowestCommonAncestor(root.left,p,q)
right = self.lowestCommonAncestor(root.right,p,q)
if not left:
return right
elif not right:
return left
# left 和 right 同时为空 or left 和 right 同时不为空
else:
return root

[1] https://www.bilibili.com/video/BV1ha4y1i7dZ?from=search&seid=15243370538903694910


About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK