leetcode题目按类型
二叉树
✅ 二叉树遍历框架
二叉树算法的设计的总路线:明确一个节点要做的事情,然后剩下的事抛给框架。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def traverse(root) :
if not root: return None
# node需要做什么在这里做, 其他的交给框架
# your task
# 前序遍历
traverse(root.left)
# 中序遍历
traverse(root.right)
# 后序遍历
/* 基本的二叉树节点 */
class TreeNode {
int val;
TreeNode left, right;
}
void traverse(TreeNode root) {
// 前序遍历
traverse(root.left)
// 中序遍历
traverse(root.right)
// 后序遍历
}
如果dfs
BST遍历框架
二叉搜索树(Binary Search Tree,简称 BST), 是一种很常用的的二叉树。它的定义是:一个二叉树中,任意节点的值要大于等于左子树所有节点的值, 且要小于等于右边子树的所有节点的值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def BST(root:TreeNode, target:int):
if root.val == target:
# do something
if root.val > target:
BST(root.left, target)
if root.val < target:
BST(root.right, target)
/* 基本的二叉树节点 */
class TreeNode {
int val;
TreeNode left, right;
}
void BST(TreeNode root, int target) {
if (root.val == target)
// 找到目标,做点什么
if (root.val < target)
BST(root.right, target);
if (root.val > target)
BST(root.left, target);
}
- 查
- 改 — 返回TreeNode类型（如root）。
N 叉树的遍历框架
二叉树框架可以扩展为 N 叉树的遍历框架:
1
2
3
4
5
6
7
8
class TreeNode:
def __init__(self, val, children):
self.val = val
self.children = chrildren
def traverse(root:TreeNode):
for child in root.children:
traverse(child)
/* 基本的 N 叉树节点 */
class TreeNode {
int val;
TreeNode[] children;
}
void traverse(TreeNode root) {
for (TreeNode child : root.children)
traverse(child)
}
图遍历框架（🚩待研究）
N 叉树的遍历又可以扩展为图的遍历,因为图就是好几 N 叉棵树的结合体。你说图是可能出现环的?这个很好办,用个布尔数组 visited 做标记就行了。
总结
做题思路
我们在做二叉树题目时候，第一想到的应该是用递归来解决。
递归返回值：
1
return root # 注意返回的是root，此时root为空
一定注意 root 是树， root.val 是值
1
valuePerDepth[index].append(root.val) # 一定注意 root 是树， root.val 是值
注意用数组形式可以把root树加入队列
1
queue = [root] # 注意用数组形式可以把root树加入队列
注意递归时, return 里的false 和true的关系, 看是and 还是or
递归法带helper函数求解标准步骤
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
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
def helper(left,right): # 注意没有self
# 基准情况，二叉树为空
if left > right: # 左右位置做标
return None
# 选中间偏左的结点为root
mid = (left+right)//2
root = TreeNode(nums[mid]) # root = TreeNode(0) # 用0作为根节点
root.left = helper(left, mid - 1)
root.right = helper(mid + 1, right)
return root
return helper(0, len(nums) - 1)
1
2
3
4
5
6
from typing import List
nums = [1,2,0,2,2]
solution = Solution()
result = solution.sortedArrayToBST(nums)
result
递归法不带helper函数标准步骤
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# 递归
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if not root: # root is empty then return, 即使子树为空也没关系应该
return None
root.left, root.right = root.right, root.left
self.invertTree(root.left)
self.invertTree(root.right)
return root # 注意返回的是root，此时root为空
迭代法标准步骤
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 迭代
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if not root:
return None
queue = [root] # 注意用数组形式可以把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
深度优先搜索
- 大多使用递归函数
- 递归函数三要素:
- 子问题原问题做相同的事情
- 需要递归结束的出口
- 递归表达
当return输出和helper子任务不同时
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 递归过程：
# 求depth（1)要求depth（2)，depth（3)
# 求depth（2)要 ‘’‘
# ’‘’
# 递归表达式：
# depth(rt) = max(depth(rt->left), depth(rt->right))+1
class Solution:
def diameterOfBinaryTree(self, root: TreeNode) -> int:
self.ans = 1
def depth(root):
if not root: return 0
self.ans = self.ans, depthdepth(root.left) + depth(root.right)+1
return max(depth(root.left), depth(root.right))+1
depth(root)
return self.ans - 1
二叉树遍历方式
二叉树遍历方法二叉树的遍历方式可以很多,如果我们限制了从左到右的习惯方式,那么主要就分为四种:
1.前序遍历规则是若二叉树为空,则空操作返回,否则先访问根结点,然后前序遍历左子树,再前序遍历右子树。如图6-8-2所示,遍历的顺序为: ABDGH-CEIF。
2.中序遍历规则是若树为空,则空操作返回,否则从根结点开始(注意并不是先访问根结点),中序遍历根结点的左子树,然后是访问根结点,最后中序遍历右子树。如图6-8-3所示,遍历的顺序为:GDHBAE-ICF。
3.后序遍历规则是若树为空,则空操作返回,否则从左到右先叶子后结点的方式遍历访问左右子树,最后是访问根结点。如图6-8-4所示,遍历的顺序为:GHDBIEFCA。
4.层序遍历规则是若树为空,则空操作返回,否则从树的第一层,也就是根结点开始访问,从上而下逐层遍历,在同一层中,按从左到右的顺序对结点逐307 个访问。如图6-8-5所示,遍历的顺序为:ABCDEFGHI。
✅101. 对称二叉树(二叉树不明白)
给定一个二叉树，检查它是否是镜像对称的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/ \
2 2
\ \
3 3
说明:
如果你可以运用递归和迭代两种方法解决这个问题，会很加分。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 自己写的 判断数组 二叉树不行
class Solution:
def isSymmetric(self, root) -> bool:
import math
length = len(root)
line_sum = math.log(length+1, 2)
# print(line_sum)
if line_sum % 1 != 0:return False
for i in range(int(line_sum)):
for j in range(int(math.pow(2,(i-1)))):
if root[int(math.pow(2,i)-1+j)] != root[int(math.pow(2,(i+1))-2-j)]:
return False
return True
1
2
3
4
5
6
7
global null
null = '#'
root = [1,2,2,null,3,null,3]
root = [1,2,2,3,4,4,3]
solution = Solution()
result = solution.isSymmetric(root)
print(result)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 递归方法
class Solution(object):
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if not root:
return True
def dfs(left,right):
# 递归的终止条件是两个节点都为空
# 或者两个节点中有一个为空
# 或者两个节点的值不相等
if not (left or right):
return True
if not (left and right):
return False
if left.val!= right.val:
return False
return dfs(left.left,right.right) and dfs(left.right,right.left)
# 用递归函数，比较左节点，右节点
return dfs(root.left,root.right)
1
2
3
4
root = [1,2,2,null,3,null,3]
solution = Solution()
result = solution.isSymmetric(root)
print(result)
2️⃣(40m)
1
2
3
4
5
6
7
8
9
10
11
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if not root: return True
def helper(root1, root2):
if not (root1 or root2): return True
elif not (root1 and root2): return False
if root1.val != root2.val: return False
return helper(root1.left, root2.right) and helper(root1.right, root2.left)
return helper(root, root)
✅104. 二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
1
2
3
4
5
6
7
8
9
10
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
1
2
3
4
5
6
7
# 树节点TreeNode定义
class TreeNode(object):
""" Definition of a binary tree node."""
def __init__(self, x):
self.val = x
self.left = None
self.right = None
1
2
3
4
5
6
7
8
9
10
11
12
13
# 递归-DFS深度搜索策略
class Solution:
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root is None:
return 0
else:
left_height = self.maxDepth(root.left)
right_height = self.maxDepth(root.right)
return max(left_height, right_height) + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 迭代
class Solution:
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
stack = []
if root is not None:
stack.append((1, root))
depth = 0
while stack != []:
current_depth, root = stack.pop()
if root is not None:
depth = max(depth, current_depth)
stack.append((current_depth + 1, root.left))
stack.append((current_depth + 1, root.right))
return depth
2️⃣(50m)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def maxDepth(self, root: TreeNode) -> int:
def helper( root, depth):
if not root:
return 0
self.maxdepth = max(self.maxdepth,depth + 1)
helper(root.left, depth + 1)
helper(root.right, depth + 1)
return self.maxdepth
self.maxdepth = 0
return helper(root, 0)
🚩(50m) 108. 将有序数组转换为二叉搜索树
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
1
2
3
4
5
6
7
8
9
10
11
示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5
2️⃣
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
if not nums: return None
# 因为是平衡二叉树, 故找中间节点
mid = len(nums)//2
node = TreeNode(nums[mid]) # 注意root是一个值!
left = nums[:mid]
right = nums[mid+1:]
node.left = sortedArrayToBST(left)
node.right = sortedArrayToBST(right)
return node
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
---------------------------------------------------------------------------
NameError Traceback (most recent call last)
<ipython-input-6-a9ae52dc2c7f> in <module>
----> 1 class Solution:
2 def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
3 if not nums: return None
4
5 # 因为是平衡二叉树, 故找中间节点
<ipython-input-6-a9ae52dc2c7f> in Solution()
1 class Solution:
----> 2 def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
3 if not nums: return None
4
5 # 因为是平衡二叉树, 故找中间节点
NameError: name 'List' is not defined
✅(50m) 226. 翻转二叉树
翻转一棵二叉树。
1
示例：输入： 4 / \ 2 7 / \ / \1 3 6 9输出： 4 / \ 7 2 / \ / \9 6 3 1
递归法不带helper函数标准步骤
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# 递归
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if not root: # root is empty then return, 即使子树为空也没关系应该
return None
root.left, root.right = root.right, root.left
self.invertTree(root.left)
self.invertTree(root.right)
return root # 注意返回的是root，此时root为空
迭代法标准步骤
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 迭代
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if not root:
return None
queue = [root] # 注意用数组形式可以把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
🚩(40m) 543. 二叉树的直径
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
1
2
3
4
5
6
7
8
9
示例 :
给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
深度优先搜索
- 大多使用递归函数
- 递归函数三要素
- 子问题原问题做相同的事情
- 需要递归结束的出口
- 递归表达式
当return输出和helper子任务不同时
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 递归过程：
# 求depth（1)要求depth（2)，depth（3)
# 求depth（2)要 ‘’‘
# ’‘’
# 递归表达式：
# depth(rt) = max(depth(rt->left), depth(rt->right))+1
class Solution:
def diameterOfBinaryTree(self, root: TreeNode) -> int:
self.ans = 1
def depth(root):
if not root: return 0
self.ans = self.ans, depthdepth(root.left) + depth(root.right)+1
return max(depth(root.left), depth(root.right))+1
depth(root)
return self.ans - 1
2️⃣
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def diameterOfBinaryTree(self, root: TreeNode) -> int:
self.ans = 1
def depth(): # 返回该节点为根的子树的深度( max(L,R)+1 )
if not root: return 0
L = depth(node.left)
R = depth(node.right)
self.ans = max(self.ans, L+R+1)
return max(L,R) + 1
depth(root)
return self.ans - 1
1
✅ 102. 二叉树的层序遍历
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 (即逐层地，从左到右访问所有节点)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
示例：
二叉树：[3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
2️⃣(50m)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 递归
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
valuePerDepth = []
def helper(root, index):
if not root: return 0
if len(valuePerDepth) < index+1:
valuePerDepth.append([])
valuePerDepth[index].append(root.val) # 一定注意 root 是树， root.val 是值
L = root.left
R = root.right
if L: helper(L, index+1)
if R: helper(R, index+1)
helper(root, 0)
return valuePerDepth
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 官解，迭代
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root: return []
res = []
queue = [root]
while queue:
size = len(queue)
tmp = []
for _ in xrange(size):
r = queue.pop(0)
tmp.append(r.val)
if r.left:
queue.append(r.left)
if r.right:
queue.append(r.right)
res.append(tmp)
return res
✅ (7m) 107. 二叉树的层次遍历 II
给定一个二叉树，返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历)
1
例如：给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7返回其自底向上的层次遍历为：[ [15,7], [9,20], [3]]
1
class Solution: def levelOrderBottom(self, root: TreeNode) -> List[List[int]]: valuePerDepth = [] def helper(root, index): if not root: return 0 if len(valuePerDepth) < index+1: valuePerDepth.append([]) valuePerDepth[index].append(root.val) # 一定注意 root 是树， root.val 是值 L = root.left R = root.right if L: helper(L, index+1) if R: helper(R, index+1) helper(root, 0) valuePerDepth = valuePerDepth[::-1] # 反转数组操作 return valuePerDepth
✅617. 合并二叉树
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
1
示例 1:输入: Tree 1 Tree 2 1 2 / \ / \ 3 2 1 3 / \ \ 5 4 7 输出: 合并后的树: 3 / \ 4 5 / \ \ 5 4 7注意: 合并必须从两个树的根节点开始。
1
class Solution: def mergeTrees(self, node1: TreeNode, node2: TreeNode) -> TreeNode: if not node1: return node2 elif not node2: return node1 node1.val = node1.val + node2.val node1.left = self.mergeTrees(node1.left, node2.left) node1.right = self.mergeTrees(node1.right, node2.right) return node1
2️⃣
3️⃣(30m)
1
class Solution: def mergeTrees(self, node1: TreeNode, node2: TreeNode) -> TreeNode: if not node1: return node2 elif not node2: return node1 node = TreeNode(node1.val + node2.val) node.left = self.mergeTrees(node1.left, node2.left) node.right = self.mergeTrees(node1.right, node2.right) return node
🚩687. 最长同值路径
给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
注意：两个节点之间的路径长度由它们之间的边数表示。
1
示例 1:输入: 5 / \ 4 5 / \ \ 1 1 5输出:2示例 2:输入: 1 / \ 4 5 / \ \ 4 4 5输出:2注意: 给定的二叉树不超过10000个结点。 树的高度不超过1000。
1
class Solution(object): def longestUnivaluePath(self, root): self.ans = 0 def arrow_length(node): if not node: return 0 left_length = arrow_length(node.left) right_length = arrow_length(node.right) left_arrow = right_arrow = 0 if node.left and node.left.val == node.val: left_arrow = left_length + 1 if node.right and node.right.val == node.val: right_arrow = right_length + 1 self.ans = max(self.ans, left_arrow + right_arrow) return max(left_arrow, right_arrow) arrow_length(root) return self.ans
2️⃣
✅ 112. 路径总和
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
1
示例: 给定如下二叉树，以及目标和 sum = 22， 5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
2️⃣ (20m)
1
class Solution: def hasPathSum(self, root: TreeNode, sum: int) -> bool: if not root: return False if root.val == sum and not(root.left or root.right): return True return self.hasPathSum(root.left, sum-root.val) or self.hasPathSum(root.right, sum-root.val)
🚩257. 二叉树的所有路径
给定一个二叉树，返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
1
示例:输入: 1 / \2 3 \ 5输出: ["1->2->5", "1->3"]解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
1
# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution: def binaryTreePaths(self, root: TreeNode) -> List[str]: if not root: return [] ans = [] path = '' def dfs(root, path): if root: path+=str(root.val) if not(root.left or root.right): ans.append(path) else: path += '->' dfs(root.left, path) dfs(root.right, path) dfs(root,path) return ans
2️⃣(30m)
注意：
- dfs 找路径时，除了传入当前节点（
node），还要传入path.
🚩669. 修剪二叉搜索树
给定一个二叉搜索树，同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。
1
示例 1:输入: 1 / \ 0 2 L = 1 R = 2输出: 1 \ 2示例 2:输入: 3 / \ 0 4 \ 2 / 1 L = 1 R = 3输出: 3 / 2 / 1
2️⃣(40m)
令 trim(node) 作为该节点上的子树的理想答案,进行构建
✅(40m) 538. 把二叉搜索树转换为累加树
给定一个二叉搜索树（Binary Search Tree)，把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
1
例如：输入: 原始二叉搜索树: 5 / \ 2 13输出: 转换为累加树: 18 / \ 20 13
2️⃣ # 一定注意，此题要用全局变量，而不能只是传参
1
# 一定注意，此题要用全局变量，而不能只是传参class Solution: def convertBST(self, root: TreeNode) -> TreeNode: def helper(node, ): global nums_sum if not node: return None helper(node.right,) # 中序 nums_sum += node.val node.val = nums_sum # ? helper(node.left,) global nums_sum nums_sum = 0 helper(root) return root# class Solution:# def convertBST(self, root: TreeNode) -> TreeNode:# def helper(node, nums_sum):# if not node:# return None# helper(node.right,nums_sum)# # 中序 # nums_sum += node.val# node.val = nums_sum # ?# helper(node.left,nums_sum) # nums_sum = 0# helper(root, nums_sum)# return root
✅ (20m) 199. 二叉树的右视图
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例:
1
输入: [1,2,3,null,5,null,4]输出: [1, 3, 4]解释: 1 <--- / \2 3 <--- \ \ 5 4 <---
2️⃣
cur = stack.pop(0) # 一定注意是pop(0)
1
class Solution: def rightSideView(self, root: TreeNode) -> List[int]: if not root: return [] stack = [root] ans = [] while stack: for i in range(len(stack)): cur = stack.pop(0) # 一定注意是pop(0) if cur.left: stack.append(cur.left) if cur.right: stack.append(cur.right) ans.append(cur.val) return ans
🚩（困难）124. 二叉树中的最大路径和
给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
1
示例 1:输入: [1,2,3] 1 / \ 2 3输出: 6示例 2:输入: [-10,9,20,null,null,15,7] -10 / \ 9 20 / \ 15 7
2️⃣
✅ (10m) 102. 二叉树的层序遍历
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 (即逐层地，从左到右访问所有节点)。
2️⃣
1
class Solution: def levelOrder(self, root: TreeNode) -> List[List[int]]: if not root: return [] stack = [root] ans = [] while stack: tmp = [] for i in range(len(stack)): cur = stack.pop(0) tmp.append(cur.val) if cur.left: stack.append(cur.left) if cur.right: stack.append(cur.right) ans.append(tmp) return ans
🚩(1.0h) 95. 不同的二叉搜索树 II
给定一个整数 n，生成所有由 1 … n 为节点所组成的 二叉搜索树 。
🚩(33m) 114. 二叉树展开为链表
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
class Solution:
def flatten(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
if root == None:
return
self.flatten(root.left)
self.flatten(root.right)
#/**** 后序遍历位置 ****/
#// 1、左右子树已经被拉平成一条链表
left = root.left
right = root.right
#// 2、将左子树作为右子树
root.left = None
root.right = left
#// 3、将原先的右子树接到当前右子树的末端
p = root
while(p.right):
p = p.right
p.right = right
✅(90m)116. 填充每个节点的下一个右侧节点指针
步骤：
- 使用queue构建层序遍历
- 加循环使每层进行一次输出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def connect(self, root: 'Node') -> 'Node':
# 层序遍历
if not root: return None
queue = [root]
while queue:
for i in range(len(queue)-1):
queue[i].next = queue[i+1]
for i in range(len(queue)):
cur = queue.pop(0)
if cur.left: queue.append(cur.left)
if cur.right: queue.append(cur.right)
return root
🚩297. 序列化二叉树
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Codec:
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
s = ""
queue = []
queue.append(root)
while queue:
root = queue.pop(0)
if root:
s += str(root.val)
queue.append(root.left)
queue.append(root.right)
else:
s += "n"
s += " "
return s
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
tree = data.split()
print(tree)
if tree[0] == "n":
return None
queue = []
root = TreeNode(int(tree[0]))
queue.append(root)
i = 1
while queue:
cur = queue.pop(0)
if cur == None:
continue
cur.left = TreeNode(int(tree[i])) if tree[i] != "n" else None
cur.right = TreeNode(int(tree[i + 1])) if tree[i + 1] != "n" else None
i += 2
queue.append(cur.left)
queue.append(cur.right)
return root
2️⃣
✅(30m)103. 二叉树的锯齿形层序遍历
难度中等378
给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如：
给定二叉树 [3,9,20,null,null,15,7],
1
2
3
4
5
3
/ \
9 20
/ \
15 7
返回锯齿形层序遍历如下：
1
2
3
4
5
[
[3],
[20,9],
[15,7]
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
if not root: return []
queue = [root]
ans = []
forward = True
while queue:
size = len(queue)
temp = []
for i in range(size):
node = queue.pop(0)
temp.append(node.val) # 注意寸的是node的值
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
# queue.pop(0)
if forward == True:
ans.append(temp)
forward = False
else:
ans.append(temp[::-1])
forward = True
return ans
总结：
- 记得放temp
✅(20m)144. 二叉树的前序遍历
难度中等511
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
1
2
输入：root = [1,null,2,3]
输出：[1,2,3]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
def helper(node):
if not node:
return
ans.append(node.val)
helper(node.left)
helper(node.right)
ans = []
helper(root)
return ans
迭代法官解：🚩
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
res = list()
if not root:
return res
stack = []
node = root
while stack or node:
while node:
res.append(node.val)
stack.append(node)
node = node.left
node = stack.pop()
node = node.right
return res
✅(10m)145. 二叉树的后序遍历
难度中等517
给定一个二叉树，返回它的 后序 遍历。
示例:
1
2
3
4
5
6
7
8
输入: [1,null,2,3]
1
\
2
/
3
输出: [3,2,1]
1
2
3
4
5
6
7
8
9
10
11
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
def helper(node):
if not node:
return
helper(node.left)
helper(node.right)
ans.append(node.val)
ans = []
helper(root)
return ans
##
