1.二叉树的中序遍历：#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| # 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:
global ans = []
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
self.inorderTraversal(root.left)
ans.append(root.val)
self.inorderTraversal(root.right)
return ans
|
2.二叉树的最大深度：#
递递的归
1
2
3
4
5
6
7
8
9
10
11
12
13
| # 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 root == None:
return 0
l= self.maxDepth(root.left)
r = self.maxDepth(root.right)
return max(l,r)+1
|
3.翻转二叉树：#
依旧递递的归：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| # 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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
def invert(node):
if not node:
return
node.left,node.right = node.right,node.left
invert(node.left)
invert(node.right)
invert(root)
return root
|
4.对称二叉树#
依旧递递的归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| # 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
def isduichen(lnode,rnode)->bool:
if not lnode and not rnode:
return True
if not (lnode and rnode):
return False
if lnode.val != rnode.val or lnode.val != rnode.val:
return False
return isduichen(lnode.left,rnode.right) and isduichen(lnode.right,rnode.left)
if not root:
return True
return isduichen(root.left,root.right)
|
5.树的直径#
算各个结点的左右深度之和并维持一个最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| # 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 diameterOfBinaryTree(self, root: TreeNode) -> int:
self.ans = 1
def depth(root):
if not root: return 0
L = depth(root.left)
R = depth(root.right)
self.ans = max(self.ans, L + R + 1)
return max(L, R) + 1
depth(root)
return self.ans - 1
|
6.二叉树的层序遍历#
题目描述：#
给你二叉树的根节点 root ，返回其节点值的 层序遍历
题解：#
使用队列辅助
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| from collections import deque
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
ans = []
queue = deque([root])
while queue:
level = []
# 当前层有多少个节点
size = len(queue)
# 只处理当前层的节点
for _ in range(size):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
ans.append(level)
return ans
|
7.将有序数组转换为二叉搜索树#
题目描述：#
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树
题解：#
还是递归,我没招了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution:
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
def build(left, right):
if left > right:
return None
mid = (left + right) // 2
root = TreeNode(nums[mid])
root.left = build(left, mid - 1)
root.right = build(mid + 1, right)
return root
return build(0, len(nums) - 1)
|
8.验证二叉搜索树:#
题目描述:#
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
- 节点的左子树只包含 严格小于 当前节点的数。
- 节点的右子树只包含 严格大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
题解:#
依旧递递的归
要注意的是:不能只比较父节点和直接子节点,要为每个节点设置一个范围(我第一遍就错在这了)
1
2
3
4
5
6
7
8
9
10
11
12
| # 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 isValidBST(self, root: Optional[TreeNode],left = -inf,right = inf) -> bool:
if not root:
return True
return left < root.val < right and self.isValidBST(root.left,left,root.val) and self.isValidBST(root.right,root.val,right)
|
9.二叉搜索树中第K小的元素:#
题目描述:#
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（k 从 1 开始计数）。
题解:
我的第一想法:遍历并排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| # 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 kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
values = []
def visit(node):
if not node:
return
values.append(node.val)
visit(node.left)
visit(node.right)
visit(root)
values.sort()
return values[k-1]
|
经典解法:中序遍历加技术:
BST的中序遍历是从小到大排序的,这个是迭代版本的,实质就是写中序遍历的过程,挺简单的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
stack = []
cur = root
while True:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
k -= 1
if k == 0:
return cur.val
cur = cur.right
|
10.二叉树的右视图:#
题目描述:#
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
题解:#
超绝队列配合层序遍历:结果就是层序遍历的每一层的最后一个值
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, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
quene = deque([root])
ans = []
while quene:
level = []
for _ in range(len(quene)):
node = quene.popleft()
if node.left:
quene.append(node.left)
if node.right:
quene.append(node.right)
level.append(node.val)
ans.append(level[-1])
return ans
|
11.二叉树展开为链表:#
题目描述:#
给你二叉树的根结点 root ，请你将它展开为一个单链表：
- 展开后的单链表应该同样使用
TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。 - 展开后的单链表应该与二叉树 先序遍历 顺序相同。
题解:#
找左子树的最右节点,并把原本的右子树接到那里
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution:
def flatten(self, root: Optional[TreeNode]) -> None:
cur = root
while cur:
if cur.left:
# 找左子树最右边的节点
pre = cur.left
while pre.right:
pre = pre.right
# 原来的右子树接到这里
pre.right = cur.right
# 左子树搬到右边
cur.right = cur.left
cur.left = None
cur = cur.right
|
12.从前序与中序遍历构造二叉树(考408的来了,你们聊)#
题目描述:#
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
题解:#
思路:从先序遍历里面找到根节点,然后在中序遍历里面找到该节点,然后左边为其左子树,右边是其右子树,迭代或者递归进行
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
| class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
if not preorder:
return None
# 1. preorder 第一个节点是根
root_val = preorder[0]
root = TreeNode(root_val)
# 2. 在 inorder 中找到根的位置
index = inorder.index(root_val)
# 3. 划分左右子树
left_inorder = inorder[:index]
right_inorder = inorder[index + 1:]
# 左子树节点数量
left_size = len(left_inorder)
# 4. 递归构建左右子树
root.left = self.buildTree(
preorder[1:left_size + 1],
left_inorder
)
root.right = self.buildTree(
preorder[left_size + 1:],
right_inorder
)
return root
|
13.路径总和:#
题目描述:#
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
题解:#
暂留:
14.二叉树的最近公共祖先#
题目描述:#
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
题解:#