思路
逆向双指针
我们为两个数组分别设置一个指针
p
1
p_1
p1与
p
2
p_2
p2来作为nums1和 nums2的尾部指针。
nums1的后半部分是空的，可以直接覆盖而不会影响结果。因此可以指针设置为从后向前遍历，每次取两者之中的较大者放进nums1的最后面。
严格来说，在此遍历过程中的任意一个时刻，nums1数组中有
m
−
p
1
−
1
m - p_1 - 1
m−p1−1 个元素被放入 nums1的后半部，nums2数组中有
n
−
p
2
−
1
n - p_2 - 1
n−p2−1 个元素被放入nums1 的后半部，而在指针
p
1
p_1
p1的后面，nums1数组有
m
+
n
−
p
1
−
1
m+n-p_1-1
m+n−p1−1 个位置。由于
-
m
+
n
−
p
1
−
1
>
=
m
−
p
1
+
n
−
p
2
−
1
m+n-p_1-1>=m-p_1+n-p_2-1
m+n−p1−1>=m−p1+n−p2−1
等价于 -
p
2
>
=
−
1
p_2>=-1
p2>=−1
永远成立，因此 p 1 p_1 p1后面的位置永远足够容纳被插入的元素，不会产生 p 1 p_1 p1的元素被覆盖的情况。
# python
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
i = m-1
j = n-1
res = m + n - 1
while res >= 0:
if i >= 0 and j >= 0: # 两个nums都还有元素未遍历
# 取较大的插入nums1后部
if nums1[i] >= nums2[j]:
nums1[res] = nums1[i]
i -= 1
else:
nums1[res] = nums2[j]
j -= 1
elif j >= 0: # 如果nums1遍历完了nums2还有未遍历的元素
nums1[res] = nums2[j]
j -= 1
res -= 1
- 1 <= preorder.length <= 3000
- inorder.length == preorder.length
- -3000 <= preorder[i], inorder[i] <= 3000
- preorder 和 inorder 均无重复元素
- inorder 均出现在 preorder
- preorder 保证为二叉树的前序遍历序列
- inorder 保证为二叉树的中序遍历序列
思路
递归
通过前序遍历确定二叉树的root，就能通过中序遍历找出二叉树的左右子树，然后通过递归就能完成二叉树的构建。
inorder中，当前root的左侧的所有点就是其左子树，root的右侧的所有点就是当前root的右子树，就把这左右两堆数字想成当前root的左右2个节点就好，然后扔到函数里进行下一层的递归。
# python3
# 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 buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if not preorder or not inorder:
return None
root = TreeNode(preorder[0])
dic = dict()
for i in range(len(inorder)):
dic[inorder[i]] = i
inroot = dic[preorder[preroot]]
root.left = self.buildTree(preorder[1:inroot], inorder[inorder])
root.right = self.buildTree(preorder[inroot+1::], inorder)