记录一下几道常见的 leetcode 题目的解法，都是比较基础的题目。
leetcode-21：合并两个有序链表
题目说明：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
解题思路：迭代
可以同时遍历两个链表，对比他们的当前节点值，将较小的节点拼接到新的链表，当较短的链表遍历完成，则结束遍历，将长链表剩余的部分拼接到新的链表。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
# 定义头节点、头指针
cur = head = ListNode()
# 循环遍历两个链表，如短链表遍历结束则结束循环
while l1 and l2:
# 值小的节点拼在头节点后，并向后移动节点
if l1.val <= l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
# 向后移动头指针
cur = cur.next
# 将长链表拼接
cur.next = l1 if l1 else l2
return head.next
时间复杂度：O(n+m)，n、m 分别为两个链表的长度，因为遍历的总长度为两个链表的长度之和。
空间复杂度：O(1)，只需要常数的空间存放若干变量。
leetcode-94：二叉树的中序遍历
题目说明：给定一个二叉树的根节点 root ，返回它的 中序 遍历。
解题思路一：递归
递归打印二叉树中序遍历的节点值。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
def inOrder(root, res):
if not root: return
inOrder(root.left, res)
res.append(root.val)
inOrder(root.right, res)
res = []
inOrder(root, res)
return res
时间复杂度：O(n)，n 为二叉树节点个数，每个节点都会被访问一次。
空间复杂度：O(n)，取决于栈深度，当二叉树为链式结构时，栈的深度为 n。
解题思路二：迭代
用栈来实现递归中使用到的栈。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
# 定义栈模拟中序遍历
stack = []
# 节点值列表
res = []
# 遍历树节点
while root or stack:
while root:
# 当前节点存在则入栈
stack.append(root)
root = root.left
# 当前节点为空时出栈
root = stack.pop(-1)
res.append(root.val)
root = root.right
return res
时间复杂度：O(n)，n 为二叉树节点个数，每个节点都会被访问一次。
空间复杂度：O(n)，取决于栈深度，当二叉树为链式结构时，栈的深度为 n。
leetcode-104：二叉树的最大深度
题目说明：给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
解题思路：递归
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root:
return 0
return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
时间复杂度：O(n)，n 为节点个数，二叉树每个节点都会被遍历一次。
空间复杂度：O(h)，h 为二叉树的高度，空间复杂度取决于二叉树的高度
leetcode-206：反转链表
题目说明：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
解题思路一：迭代
运用 Python 解包赋值的方式，pre 指向当前节点 cur，pre.next 指向前节点 pre（注意，此时 pre.next 的 pre 已被赋值为 cur，而后面的 pre 还是 None），当前节点 cur 指向下一个节点 cur.next
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
pre, cur = None, head
while cur:
pre, pre.next, cur = cur, pre, cur.next
return pre
时间复杂度：O(n)，n 为链表长度，每个链表都会被遍历一次。
空间复杂度：O(1)。
解题思路二：迭代
反转时，要先保存当前节点的下一个节点，防止其丢失。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
pre, cur = None, head
while cur:
next = cur.next
cur.next = pre
pre = cur
cur = next
return pre
时间复杂度：O(n)。
空间复杂度：O(1)。
解题思路三：递归
递归可理解为先将链表递归到最后一个节点的前一个节点，结束递归时修改这个节点的指针进行操作。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
# 递归终止条件：空链表或者当前节点为尾节点，则返回，该尾节点为新链表的头节点
if not head or not head.next:
return head
new_head = self.reverseList(head.next)
# 对每个递归的节点执行以下操作：将当前节点的下一个节点的后指针指向当前节点，然后将当前节点的下一个节点置空
head.next.next = head
head.next = None
# 最后返回新链表
return new_head
时间复杂度：O(n)。
空间复杂度：O(n），n 为链表长度，递归深度最多为 n 层。
leetcode-226：翻转一颗二叉树
解题思路一：广度优先搜索
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def invertTree(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
if not root:
return None
queue = [root]
while queue:
tmp = queue.pop(0)
tmp.left, tmp.right = tmp.right, tmp.left
if tmp.left:
queue.append(tmp.left)
if tmp.right:
queue.append(tmp.right)
return root
时间复杂度：O(n)，n 为二叉树节点个数，因为每个节点都会入队出队一次。
空间复杂度：O(n)，n 为二叉树节点个数，最快情况为完全二叉树，每个叶子节点都会进队，二叉树叶子节点个数为 n/2 个，故空间复杂度为 O(n)。
解题思路二：深度优先搜索
递归交换当前节点的左右子树，当前节点为空时结束递归。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def invertTree(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
if not root:
return root
root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
return root
时间复杂度：O(n)，每个节点在递归时都会访问一次。
空间复杂度：O(n)，最坏情况是树成为链式结构，递归的深度为 n。
leetcode-617：合并二叉树
题目说明：
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。 你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
解题思路：递归
有三种情况：
- 只有一个树的节点为空，重叠时返回另一个树结点
- 都为空则返回空
- 都不为空，创建新的树节点，合并两个树节点的值作为新节点的值，并递归的合并左右子树
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
if not root1:
return root2
if not root2:
return root1
merged = TreeNode(root1.val+root2.val)
merged.left = self.mergeTrees(root1.left, root2.left)
merged.right = self.mergeTrees(root1.right, root2.right)
return merged
时间复杂度：O(min(n, m))，仅在两棵二叉树节点都不为空时才做合并处理，故被访问到的节点数不超过较小的二叉树节点数。
空间复杂度：O(min(n, m))，栈的深度为二叉树高度，递归的层数不会超过较小的二叉树的高度，最坏情况下树为链式结构，高度等于节点数。
leetcode-897：递增顺序搜索树
题目说明：给你一棵二叉搜索树，请你 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。
解题思路：中序遍历后生成新树
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def increasingBST(self, root: TreeNode) -> TreeNode:
# 定义一个中序遍历函数，将树节点保存到列表中
def inOrder(root: TreeNode, res: list):
if not root: return root
inOrder(root.left, res)
res.append(root.val)
inOrder(root.right, res)
res = []
inOrder(root, res)
cur = dummy = TreeNode(-1)
# 列表生成只有右节点的二叉树
for val in res:
cur.right = TreeNode(val)
cur = cur.right
return dummy.right
时间复杂度：O(n)，n 为二叉树节点数，每个节点都会遍历两次，故为 O(n)。
空间复杂度：O(n)，n 为二叉树节点数，需要长度为n的列表保存所有节点的值。
leetcode-938：二叉搜索树的范围和
题目说明：给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。
解题思路一：深度优先搜索
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
# 空节点返回0
if not root:
return 0
if root.val < low:
return self.rangeSumBST(root.right, low, high)
elif root.val > high:
return self.rangeSumBST(root.left, low, high)
# 返回当前节点的值并且遍历左右子树
else:
return root.val + self.rangeSumBST(root.left, low, high) + self.rangeSumBST(root.right, low, high)
时间复杂度：O(n)
空间复杂度：O(n)
解题思路二：广度优先搜索
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
# 把当前节点加入队列
queue = [root]
sum = 0
# 遍历队列
while len(queue):
# 弹出队列中第一个节点
root = queue.pop(0)
# 逐层把该节点的左节点或右节点加入队列
if root.left:
queue.append(root.left)
if root.right:
queue.append(root.right)
if low <= root.val <= high:
sum += root.val
return sum
时间复杂度：O(n)
空间复杂度：O(n)
解题思路三：前序遍历求和
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
def preOrder(root, l):
if not root:
return
l.append(root.val)
preOrder(root.left, l)
preOrder(root.right, l)
l = []
# 前序遍历将链表值存入list
preOrder(root, l)
sum = 0
# 遍历list求和
for i in l:
if low <= i <= high:
sum += i
return sum
时间复杂度：O(n)
空间复杂度：O(n)
