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

1. lc 231 - 2的幂

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

1.1 解题思路 - 位运算

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

[1]

代码

1
2
3
4
5
6
7
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)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 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) 大小的额外空间。

代码

# Definition for a binary tree node.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 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 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# 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