1. 翻转二叉树
翻转一棵二叉树。
示例 1：
输入：
4
/ \
2 7
/ \ / \
1 3 6 9
输出：
4
/ \
7 2
/ \ / \
9 6 3 1
示例 2：
输入：
1
/ \
2 3
/ / \
4 5 6
\
7
输出：
1
/ \
3 2
/ \ \
6 5 4
/
7
代码：
class TreeNode: def __init__(self, val): self.val = val self.left = None self.right = None class Solution(object): def invertTree(self, root): """ :type root: TreeNode :rtype: TreeNode """ if not root: return None root.left, root.right = root.right, root.left self.invertTree(root.left) self.invertTree(root.right) return root def listToTree(lst: list) -> TreeNode: if not lst: return None root = TreeNode(lst[0]) queue = [root] i = 1 while i < len(lst): node = queue.pop(0) if lst[i] is not None: node.left = TreeNode(lst[i]) queue.append(node.left) i += 1 if i < len(lst) and lst[i] is not None: node.right = TreeNode(lst[i]) queue.append(node.right) i += 1 return root def inorderTraversal(root: TreeNode) -> list: if not root: return [] res = [] res += inorderTraversal(root.left) res.append(root.val) res += inorderTraversal(root.right) return res # %% s = Solution() lst = [4, 2, 7, 1, 3, 6, 9] root = listToTree(lst) print(inorderTraversal(root)) root = s.invertTree(root) print(inorderTraversal(root)) lst = [1, 2, 3, 4, None, 5, 6, None, None, None, None, None, 7] root = listToTree(lst) print(inorderTraversal(root)) root = s.invertTree(root) print(inorderTraversal(root))
输出：
[1, 2, 3, 4, 6, 7, 9]
[9, 7, 6, 4, 3, 2, 1]
[4, 2, 1, 5, 3, 6, 7]
[7, 6, 3, 5, 1, 2, 4]
翻转二叉树的非递归实现：
def invertTree(root: TreeNode) -> TreeNode: if not root: return None stack = [root] while stack: node = stack.pop() if node: node.left, node.right = node.right, node.left stack.append(node.left) stack.append(node.right) return root
2. 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1：
输入：strs = ["flower","flow","flight"]
输出："fl"
示例 2：
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。
提示：
0 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成
代码：
from typing import List class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: if len(strs) == 0: return '' i = 0 lcp = [] while True: done = False if i >= len(strs[0]): break j = 0 while j < len(strs): if i < len(strs[j]): if strs[j][i] != strs[0][i]: done = True break else: done = True break j += 1 if not done: lcp.append(strs[0][i]) i += 1 else: break return ''.join(lcp) # %% s = Solution() print(s.longestCommonPrefix(strs = ["flower","flow","flight"]))
输出：
fl
3. 2的幂
给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。
如果存在一个整数 x 使得 n == 2^x ，则认为 n 是 2 的幂次方。
示例 1：
输入：n = 1
输出：true
解释：20 = 1
示例 2：
输入：n = 16
输出：true
解释：24 = 16
示例 3：
输入：n = 3
输出：false
示例 4：
输入：n = 4
输出：true
示例 5：
输入：n = 5
输出：false
提示：
-2^31 <= n <= 2^31 - 1
进阶：你能够不使用循环/递归解决此问题吗？
代码：
class Solution: def isPowerOfTwo(self, n): z = bin(n)[2:] if z[0] != "1": return False for item in z[1:]: if item != "0": return False return True # %% s = Solution() print(s.isPowerOfTwo(1)) print(s.isPowerOfTwo(16)) print(s.isPowerOfTwo(3)) print(s.isPowerOfTwo(4)) print(s.isPowerOfTwo(5))
输出：
True
True
False
True
False
