文章目录
- 102. 二叉树的层序遍历
- 104. 二叉树的最大深度
- 105. 从前序与中序遍历序列构造二叉树
- 114. 二叉树展开为链表
- 121. 买卖股票的最佳时机
102. 二叉树的层序遍历
# 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
from collections import deque
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root: return []
q = deque([root])
res = []
while q:
tmp = []
for i in range(len(q)):
node = q.popleft()
tmp.append(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
res.append(tmp)
return res
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: Optional[TreeNode]) -> int:
if not root: return 0
left_height = self.maxDepth(root.left)
right_height = self.maxDepth(root.right)
return max(left_height, right_height) + 1
说实话，看着这题很简单，其实我知道答案，再写也没写出来，有时候看着简单的题，其实需要很多的思考过程才能写出来。代码简单不代表真的简单。
def maxDepth(self, root):
if not root: return 0
left_height = self.maxDepth(root.left)
right_height = self.maxDepth(root.right)
return max(left_height, right_height) + 1
105. 从前序与中序遍历序列构造二叉树
如果手写我知道怎么弄，但是写代码不知道怎么将左右子树分开。
尝试写了一下，还是没写出来：
# 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
preleft, preright = 0, len(preorder) - 1
inleft, inright = 0, len(inorder) - 1
pivot_index = inorder.index(preorder[preleft])
root = TreeNode(val = inorder[pivot_index])
root.left = buildTree(preorder[preleft + 1: pivot_index - inleft + preleft + 1)
root.right = buildTree(pivot_index - inleft + preleft + 1: preright + 1)
return root
下面是答案：
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
def myBuildTree(preorder_left: int, preorder_right: int, inorder_left: int, inorder_right: int):
if preorder_left > preorder_right:
return None
# 前序遍历中的第一个节点就是根节点
preorder_root = preorder_left
# 在中序遍历中定位根节点
inorder_root = index[preorder[preorder_root]]
# 先把根节点建立出来
root = TreeNode(preorder[preorder_root])
# 得到左子树中的节点数目
size_left_subtree = inorder_root - inorder_left
# 递归地构造左子树，并连接到根节点
# 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
root.left = myBuildTree(preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1)
# 递归地构造右子树，并连接到根节点
# 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
root.right = myBuildTree(preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right)
return root
n = len(preorder)
# 构造哈希映射，帮助我们快速定位根节点
index = {element: i for i, element in enumerate(inorder)}
return myBuildTree(0, n - 1, 0, n - 1)
尝试写了下，还是不行
# 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
n = len(preorder)
index = {element: ind for ind, element in enumerate(inorder)}
def mybuildTree(preorder, preleft, preright, inleft, inright):
if preleft > preright or inleft > inright:
return
root = TreeNode(val = preorder[preleft])
pivot_index = index[preorder[preleft]]
root.left = mybuildTree(preorder, preleft + 1, pivot_index - inleft + preleft + 1, inleft, pivot_index)
root.right = mybuildTree(preorder, pivot_index - inleft + preorder + 1, preright + 1, pivot_index + 1, inright + 1)
return root
return mybuildTree(preorder, 0, n - 1, 0, n - 1)
先跳过吧，回头再来补
第二遍过来写了，能写出来了，但是还是看着答案写的：
# 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]):
def buildT(pre_left, pre_right, in_left, in_right):
if pre_left > pre_right:
return
root_val = preorder[pre_left]
root = TreeNode(root_val)
in_index = index[root_val]
size = in_index - in_left
root.left = buildT(pre_left + 1, pre_left + size, in_left, in_index - 1)
root.right = buildT(pre_left + size + 1, pre_right, in_index + 1, in_right)
return root
n = len(preorder)
index = {ele:ind for ind, ele in enumerate(inorder)}
return buildT(0, n - 1, 0, n - 1)
114. 二叉树展开为链表
能把列表通过dfs输出，但是不会构建。。。。我感觉自己是个弱智
# 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
from collections import deque
class Solution:
def flatten(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
res = deque()
def dfs(root, res):
if not root:
return
res.append(root.val)
if root.left:
dfs(root.left, res)
if root.right:
dfs(root.right, res)
dfs(root, res)
dummy = root1 = TreeNode(res.popleft())
while res:
root1.right = TreeNode(res.popleft())
root1 = root1.right
return dummy
下面是官方答案：他用的prev和curr，我不知道怎么做的。我知道我为什么错了，这道题需要原地改变，而不是新建一个树。所以没有return，他就是看root。下面他加入list是root节点，而不是节点的值。
class Solution:
def flatten(self, root: TreeNode) -> None:
preorderList = list()
def preorderTraversal(root: TreeNode):
if root:
preorderList.append(root)
preorderTraversal(root.left)
preorderTraversal(root.right)
preorderTraversal(root)
size = len(preorderList)
for i in range(1, size):
prev, curr = preorderList[i - 1], preorderList[i]
prev.left = None
prev.right = curr
下面是我改的
# 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 flatten(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
res = []
def dfs(root):
if not root:
return
res.append(root)
if root.left:
dfs(root.left)
if root.right:
dfs(root.right)
dfs(root)
for i in range(1, len(res)):
pre, cur = res[i - 1], res[i]
pre.left = None
pre.right = cur
第二遍：先用dfs遍历，然后把root都加入到列表中，然后在重新把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 flatten(self, root: TreeNode):
li = []
def dfs(root):
if not root:
return
li.append(root)
if root.left: dfs(root.left)
if root.right: dfs(root.right)
dfs(root)
for i in range(len(li) - 1):
root = li[i]
root.left = None
root.right = li[i + 1]
进阶的版本需要在原树上更改，这就需要用到递归了。
class Solution:
def flatten(self, root: TreeNode) -> None:
if not root:
return
stack = [root]
prev = None
while stack:
curr = stack.pop()
if prev:
prev.left = None
prev.right = curr
left, right = curr.left, curr.right
if right:
stack.append(right)
if left:
stack.append(left)
prev = curr
121. 买卖股票的最佳时机
通过了，但是我感觉我的思路不是按照老师讲的dp的思路写的。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices or len(prices) == 0:
return 0
n = len(prices)
dp = [0] * (n + 1)
min_val = float('inf')
for i in range(n):
min_val = min(min_val, prices[i])
dp[i] = prices[i] - min_val
return max(dp)
这个答案的思路和我想的一样
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
if n == 0: return 0 # 边界条件
dp = [0] * n
minprice = prices[0]
for i in range(1, n):
minprice = min(minprice, prices[i])
dp[i] = max(dp[i - 1], prices[i] - minprice)
return dp[-1]
