算法题第四篇
# 二叉树
https://zhuanlan.zhihu.com/p/29800274
类型题：
1.前序遍历、中序遍历、后续遍历
2.层次遍历：层次遍历和之字形遍历
3.使用前序遍历、中序遍历和后续遍历中的两种构建二叉树
4.求和问题：判断二叉树中是否存在
5.填充问题：二叉树的右侧指针1、2
6.一般二叉树的特殊情况：相同二叉树、对称二叉树
7.搜索二叉树：是否为二叉树、
8.其他：平衡二叉树、二叉树的最近公共祖先
# 循环遍历写法
qianxubianli
def traverse_circulation(root):
stack = []
node = root
while node or len(stack) != 0:
print(node.data)
stack.append(node)
node = node.left
while (not node ) and len(stack) != 0:
node = stack.pop()
node = node.right
2
3
4
5
6
7
8
9
10
# 判断是否为对称二叉树 101
class solution
def isSymmetric(self,root)
if not root:
return True
def sub(left,right):
if not left and not right:
return True
if not left or not right:
return False
return left.val == right.val and sub(left.left,right.right) and sub(left.right,right.left)
return sub(root.left,root.right)
2
3
4
5
6
7
8
9
10
11
# 二叉树的镜像翻转(951)1828
输入一个二叉树，该函数输出它的镜像。
例：输入root = [4,2,7,1,3,6,9]
输出[4,7,2,9,6,3,1]
使用递归实现
class Solution:
def mirrorTree(self, root: TreeNode) -> TreeNode:
# 用递归可以实现
if root == None:
return None
root.left,root.right = root.right,root.left
self.mirrorTree(root.left)
self.mirrorTree(root.right)
return root
2
3
4
5
6
7
8
9
10
# 判断是否是子树
class Solution:
def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
if A==None or B==None:
return False
def check(A:TreeNode,B:TreeNode)->bool:
return A!=None and A.val==B.val and (True if B.left==None else check(A.left,B.left)) and (True if B.right==None
else check(A.right,B.right))
return check(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B)
2
3
4
5
6
7
8
9
# 相同的树(100)
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
例：输入：p = [1,2,3],q = [1,2,3]
输出：true
class Solution:
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
if not p and not q:
return True
elif p is not None and q is not None:
if p.val == q.val:
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
else:
return False
else:
return False
2
3
4
5
6
7
8
9
10
11
# 二叉树的所有路径(257)
给定一个二叉树，返回所有从根节点到叶子节点的路径。
依然是递归
class Solution:
def binaryTreePaths(self, root: TreeNode) -> List[str]:
if not root:
return []
if not root.left and not root.right:
return [str(root.val)]
paths = []
if root.left:
for i in self.binaryTreePaths(root.left):
paths.append(str(root.val) + '->' + i)
if root.right:
for i in self.binaryTreePaths(root.right):
paths.append(str(root.val) + '->' + i)
return paths
2
3
4
5
6
7
8
9
10
11
12
13
14
# 二叉树的最近公共祖先236
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
例：输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
class Solution:
def lowestCommonAncestor(self,root:'TreeNode',p:'TreeNode',q:'TreeNode')->'TreeNode':
if(root == None):
return None
if root == p or root == q:
return root
m = self.lowestCommonAncestor(root.left,p,q)
n = self.lowestCommonAncestor(root.right,p,q)
if(m and n):
return root
elif m:
return m
else
return n
2
3
4
5
6
7
8
9
10
11
12
13
14
# 二叉树的最大路径和(124)
路径和为路径中各节点值的总和。
class Solution:
def maxPathSum(self,root:TreeNode)->int:
self.res = float('inf')
def dfs(root):
if not root:
return 0
left = max(0,dfs(root.left))
right = max(0,dfs(root.right))
val = root.val + left + right
self.res = max(self.res,val)
return root.val+max(left,right)
dfs(root)
return self.res
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 二叉树的最大深度(104)
给定一个二叉树，找出其最大深度
class Solution:
def TreeDepth(self,pRoot):
if not pRoot:
return 0
depthleft = self.TreeDepth(pRoot.left)
depthright = self.TreeDepth(pRoot.right)
return max(depthleft,depthright) +1
2
3
4
5
6
7
# 二叉树的最小深度(111)
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
例：输入：root = [3,9,20,null,null,15,7]
输出：2
class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root:
return 0
left = self.minDepth(root.left);
right = self.minDepth(root.right);
return min(left,right) + 1;
2
3
4
5
6
7
# 平衡二叉树(110)
给定一个二叉树，判断它是否是高度平衡的二叉树。
一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
例：输入：root = [3,9,20,null,null,15,7]
输出：true
DFS
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
if root is None: return True
def dfs(root):
if root is None:
return 0
return max(dfs(root.left),dfs(root.right))+1
return abs(dfs(root.left)-dfs(root.right))<=1 and self.isBalanced(root.left) and self.isBalanced(root.right)
2
3
4
5
6
7
8
9
10
# 填充每一个节点的下一个右侧指针(116、117)
给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
例如：输入：root = [1,2,3,4,5,6,7]
输出：root=[1,#,2,3,#,4,5,6,7,#]
递归解法
##解法1
class Solution:
def connect(self, root: 'Node') -> 'Node':
if not root: return
if root.right:
root.left.next = root.right
if root.next:
root.right.next = root.next.left
self.connect(root.left)
self.connect(root.right)
return root
##解法2
class Solution:
def connect(self, root: 'Node') -> 'Node':
if root:
l, r = root.left, root.right
while l:
l.next, l, r = r, l.right, r.left
self.connect(root.left)
self.connect(root.right)
return root
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
117:如果不是完美二叉树是普通二叉树
class Solution:
def connect(self, root: 'Node') -> 'Node':
a = root
while a:
head = tail = Node(0) # 下一层的虚拟头尾节点
while a:
if a.left:
tail.next = a.left
tail = tail.next
if a.right:
tail.next = a.right
tail = tail.next
a = a.next # 核心，要想达到常数空间复杂度，必须利用已建立的信息
a = head.next
return root
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 二叉树的前序144、中序94、后序遍历145
前序遍历
给你二叉树的根节点，返回它节点的前序遍历
例：输入：root = [1,null,2,3]
输出：[1,2,3]
前序遍历的“前”指的是先访问根结点，然后依次访问它的左孩子和右孩子，最终遍历整一颗树。
递归
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return root
buff, ret = [root], []
while buff:
f = buff.pop()
if f.right: buff.append(f.right)
if f.left: buff.append(f.left)
ret.append(f.val)
return ret
2
3
4
5
6
7
8
9
10
11
12
中序遍历
给定一个二叉树的根节点 root ，返回它的 中序 遍历。
例：输入：[1,null,2,3]
输出：[1,3,2]
中序遍历 先遍历左子树->根节点->右子树,
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
ans = []
def inorder(root):
if not root:
return
inorder(root.left)
ans.append(root.val)
inorder(root.right)
inorder(root)
return ans
2
3
4
5
6
7
8
9
10
11
后序遍历
给定一个二叉树，返回它的 后序 遍历。
例：输入:[1,null,2,3]
输出：[3,2,1]
后序遍历的顺序是每次遍历左孩子，再遍历右孩子，最后遍历根节点。
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return
ans = []
def inorder(root):
if not root:
return
inorder(root.left)
inorder(root.right)
ans.append(root.val)
inorder(root)
return ans
2
3
4
5
6
7
8
9
10
11
12
13
# 层序遍历(102、107)
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）
例：输入：[3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]]
BFS、队列实现
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
res = []
if root == None:
return res
q = [root]
while len(q) != 0:
res.append([node.val for node in q])
new_q = []
for node in q:
if node.left:
new_q.append(node.left)
if node.right:
new_q.append(node.right)
q = new_q
return res
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 从最下层输出到根节点
# 之字形打印二叉树(103)
给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例：输入给定二叉树：[3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]
先层序遍历，再中间翻转
class Solution:
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
stack = []
def levelOrder(root, depth, stack):
if not root:
return
if depth >= len(stack):
stack.append([])
stack[depth].append(root.val)
levelOrder(root.left, depth + 1, stack)
levelOrder(root.right, depth + 1, stack)
levelOrder(root, 0, stack)
for i in range(1, len(stack), 2):
stack[i] = stack[i][::-1]
return stack
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 路径总和(112)
给定二叉树的根节点root和一个表示目标的整数,判断该数中是否存在根节点到叶子节点的路径，这条路径上所有的节点值相加等于目标和target
例：输入：root=[1,2,3],targetSum = 5
输出：false
class Solution:
def hasPathSum(self,root:TreeNode,targetSum:int)->bool:
self.m = false;
def dfs(node,s):
if not node:
return
else:
s += node.val;
dfs(node.left,s)
dfs(node.right,s)
if not node.left and not node.right and s == sum:
self.m = True
dfs(root,0)
return self.m
2
3
4
5
6
7
8
9
10
11
12
13
14
# 路径总和2(113)
给定二叉树的根节点root和一个表示目标和的整数,找出所有从根节点到叶子节点路径总和等于给定目标的路径
例：输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1],targetSum = 22
输出：[5,4,11,2],[5,8,4,5]
class Solution:
def pathSum(self,root:TreeNode,targetSum:int)->List[List[int]]:
a = []
if not root:
return []
def dfs(root,al):
if root.right:
dfs(root.right,al+[root.right.val])
if root.left:
dfs(root.left,al+[root.left.val])
if not root.right and not root.left:
if sum(al) == targetSum:
a.append(al)
dfs(root,[root.val])
return a
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 二叉树展开生成链表114
给你二叉树的节点root，将它展开为一个单链表
1.展开后的单链表同样适用treenode，其中right子指针指向链表的下一节点，而左指针始终为null
2.展开后的单链表应该与二叉树先序遍历顺序相同
输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]
class Solution:
def flatten(self, root: TreeNode) -> None:
if not root or (not root.left and not root.right):
return root
#先把左右子树捋直
self.flatten(root.left)
self.flatten(root.right)
tmp = root.right #把捋直的右子树备份一下
root.right = root.left #把捋直的左子树放到右边
root.left = None #记得把左子树置空
while(root.right): #找到现在右子树的最后一个node
root = root.right
root.right = tmp #把捋直的原来的右子树接上去
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 根节点到叶节点数字之和(129)
给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字，计算从根节点到叶节点生成的 所有数字之和 。
例：输入：root = [1,2,3]
输出：25，12 + 13 = 25
class Solution:
def sumNumbers(self, root: TreeNode) -> int:
def dfs(root, s):
if not root: return
if not root.left and not root.right:
ans.append(s + str(root.val))
dfs(root.left, s + str(root.val))
dfs(root.right, s + str(root.val))
ans = []
dfs(root, '')
res = 0
for i in ans:
res += int(i)
return res
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 二叉树的直径(543)
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
class Solution:
def diameterOfBinaryTree(self, root: TreeNode) -> int:
def deapth(node: TreeNode) -> int:
nonlocal ma
if not node:
return 0
l = deapth(node.left)
r = deapth(node.right)
ma = max(l + r, ma)
return max(l, r) + 1
ma = 0
deapth(root)
return ma
2
3
4
5
6
7
8
9
10
11
12
13
# 二叉树的坡度563
给定一个二叉树，计算 整个树 的坡度 。
一个树的 节点的坡度 定义即为，该节点左子树的节点之和和右子树节点之和的 差的绝对值 。如果没有左子树的话，左子树的节点之和为 0 ；没有右子树的话也是一样。空结点的坡度是 0 。
整个树 的坡度就是其所有节点的坡度之和。
输入：root = [1,2,3]
输出：1
class Solution:
def findTilt(self, root: TreeNode) -> int:
res=0
def f(node):
nonlocal res
if not node:
return 0
l,r=f(node.left),f(node.right)
res+=abs(l-r)
return node.val+l+r
f(root)
return res
2
3
4
5
6
7
8
9
10
11
12
# 二叉树最大宽度(662)
给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。
每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。
class Solution:
def widthOfBinaryTree(self, root: TreeNode) -> int:
queue = [(root,0)] # (a, b) 节点，位置
res = 0
while queue:
arr = []
for _ in range(len(queue)):
node,pos = queue.pop(0)
arr.append(pos)
if node.left:
queue.append((node.left,pos*2))
if node.right:
queue.append((node.right,pos*2+1))
res = max(res,1+arr[-1]-arr[0])
return res
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 二叉树的右视图199
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值
输入：[1,2,3,null,5,null,4]
输出：[1,3,4]
此题前序遍历、后序遍历、层次遍历均可，遍历取值，此为后序遍历
class Solution:
def rightSideView(self,root:TreeNode)->List[int]:
d = []
def f(r, i):
if r:
i == len(d) and d.append(r.val)
f(r.right, i + 1)
f(r.left, i + 1)
f(root, 0)
return d
2
3
4
5
6
7
8
9
10
# 从前序与中序遍历序列构造二叉树(105)
根据一棵树的前序遍历与中序遍历构造二叉树。
注意：你可以假设树中没有重复的元素。
例：输入：preorder = [3,9,20,15,7]，inorder = [9,3,15,20,7]
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if not preorder:
return None
x = preorder.pop(0)
node = TreeNode(x)
i = inorder.index(x)
node.left = self.buildTree(preorder[:i], inorder[:i])
node.right = self.buildTree(preorder[i:], inorder[i+1:])
return node
2
3
4
5
6
7
8
9
10
11
12
# 从中序和后序遍历序列构造二叉树(106)
根据一棵树的中序遍历与后序遍历构造二叉树。 注意：你可以假设树中没有重复的元素。
例：输入：inorder = [9,3,15,20,7]，postorder = [9,15,7,20,3]
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
if not postorder:
return None
root = TreeNode(postorder[-1])#创建树
n = inorder.index(root.val)
root.left = self.buildTree(inorder[:n],postorder[:n])
root.right = self.buildTree(inorder[n+1:],postorder[n:-1])
return root
2
3
4
5
6
7
8
9
# 二叉树剪枝(814)
给定二叉树根结点 root ，此外树的每个结点的值要么是 0，要么是 1。
返回移除了所有不包含 1 的子树的原二叉树。
例：输入：[1,null,0,0,1]
输出：[1,null,0,null,1]
class Solution:
def pruneTree(self, root: TreeNode) -> TreeNode:
if not root:
return None
root.left=self.pruneTree(root.left)
root.right=self.pruneTree(root.right)
if root.val==0 and not root.left and not root.right:
return None
return root
2
3
4
5
6
7
8
9
# 有序数组转换二叉搜索树(108)
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
例：输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]或者[0,-10,5,null,-3,null,9]
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
if not nums:
return None
else:
mid=len(nums)//2
tn=TreeNode(nums[mid])
nums1=nums[0:mid]
nums2=nums[mid+1:len(nums)]
tn.left=self.sortedArrayToBST(nums1)
tn.right=self.sortedArrayToBST(nums2)
return tn
2
3
4
5
6
7
8
9
10
11
12
# 有序链表转换二叉搜索树(109)
给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
例：输入：[10,-3,0,5,9]
输出：答案不止一个，其中一个是[0,-3,9,-10,null,5]
class Solution:
def sortedListToBST(self, head: ListNode) -> TreeNode:
if not head:
return None
if not head.next:
return TreeNode(head.val)
fast = slow = last = head
while fast and fast.next:
last = slow
slow = slow.next
fast = fast.next.next
node = TreeNode(slow.val)
node.right = self.sortedListToBST(slow.next)
last.next = None
node.left = self.sortedListToBST(head)
return node
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 不同的二叉搜索树2(95)
给定一个整数 n，生成所有由 1 ... n 为节点所组成的 二叉搜索树
例：输入：3
输出：[ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3], [1,null,2,null,3] ]
class Solution:
def generateTrees(self, n: int) -> List[TreeNode]:
2
3
# 不同的二叉搜索树(96)
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
例：输入：n = 3
输出：5
class Solution:
def numTrees(self, n: int) -> int:
dp = [0] * (n+1)
dp[0] = 1
dp[1] = 1
for i in range(2,n+1):
for j in range(1,i+1):
dp[i] += dp[j-1] * dp[i-j]
return dp[n]
2
3
4
5
6
7
8
9
10
# 验证二叉搜索树(98)
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
def zcc(root):
if not root:
return []
left = zcc(root.left)
right = zcc(root.right)
return left + [root.val] + right
ret = zcc(root)
return ret == sorted(ret) and len(ret) == len(set(ret))
2
3
4
5
6
7
8
9
10
# 恢复二叉搜索树(99)
# 完全二叉树的节点个数(222)
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
例：输入：[1,2,3,4,5,6]
输出：6
class Solution:
def countNodes(self, root: TreeNode) -> int:
if not root: return 0
return self.countNodes(root.left) + self.countNodes(root.right) + 1
2
3
4
# 二叉搜索树第k小的元素(230)
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
例：输入：root = [5,3,6,2,4,null,null,1], k = 3 输出：3
class Solution:
def kthSmallest(self, root: TreeNode, k: int) -> int:
def dfs(root: TreeNode):
nonlocal res, cnt
if res != -1 or not root: return
dfs(root.left)
cnt += 1
if cnt == k: res = root.val
dfs(root.right)
res, cnt = -1, 0
dfs(root)
return res
2
3
4
5
6
7
8
9
10
11
12
13
# 二叉搜索树的最近公共祖先235
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
输入：root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出：6
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if p.val<root.val and q.val<root.val:
return self.lowestCommonAncestor(root.left,p,q)
if p.val>root.val and q.val>root.val:
return self.lowestCommonAncestor(root.right,p,q)
return root
2
3
4
5
6
7
8
9
10
# 二叉搜索树的最小绝对差(530)
给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。
class Solution:
def getMinimumDifference(self, root: TreeNode) -> int:
inorder = []
def dfs(root):
nonlocal inorder
if not root:
return
dfs(root.left)
inorder.append(root.val)
dfs(root.right)
dfs(root)
return min([inorder[i]-inorder[i-1] for i in range(1,len(inorder))])
2
3
4
5
6
7
8
9
10
11
12
# 二叉搜索树中的插入操作(701)
给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
例：输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]
class Solution:
def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
if root == None:
return TreeNode(val)
if val < root.val:
root.left = self.insertIntoBST(root.left, val)
else:
root.right = self.insertIntoBST(root.right, val)
return root
2
3
4
5
6
7
8
9
# 把二叉树转换为累加树(538.1038)
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
例：输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
迭代
class Solution:
def __init__(self):
self.num = 0
def convertBST(self, root: TreeNode) -> TreeNode:
if not root:
return root
# 性质: 中序遍历从小到大
self.convertBST(root.right)
# 前缀和
root.val += self.num
self.num = root.val
self.convertBST(root.left)
return root
2
3
4
5
6
7
8
9
10
11
12
13
# 合并二叉树(617)
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
class Solution:
def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
if root1 and root2 :
root1.val += root2.val
root1.left = self.mergeTrees(root1.left, root2.left)
root1.right = self.mergeTrees(root1.right, root2.right)
return root1
return root1 or root2
2
3
4
5
6
7
8
# 二叉树的层平均值(637)
给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。
class Solution:
def averageOfLevels(self, root: TreeNode) -> List[float]:
ans, level = [], root and [root]
while level:
ans.append(sum(n.val for n in level) / len(level))
level = [k for n in level for k in (n.left, n.right) if k]
return ans
2
3
4
5
6
7
# 二叉树中所有距离为K的点(863)
给定一个二叉树（具有根结点 root）， 一个目标结点 target ，和一个整数值 K 。
返回到目标结点 target 距离为 K 的所有结点的值的列表。
例：输入：root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2
输出：[7,4,1]
树转图
class Solution:
def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
parent_map = {}
def findParents(node, parent):
if not node:
return
parent_map[node] = parent
findParents(node.left, node)
findParents(node.right, node)
findParents(root, None)
visited = [target.val]
def findDisK(node, K, visited):
if not node: return []
if K == 0: return [node.val]
res = []
for nextNode in [node.left, node.right, parent_map[node]]:
if nextNode and nextNode.val not in visited:
visited.append(nextNode.val)
sub_res = findDisK(nextNode, K-1, visited)
for r in sub_res:
res.append(r)
return res
return findDisK(target, K, visited)
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
满二叉树
如果一棵二叉树的结点要么是叶子结点，要么它有两个子结点，这样的树就是满二叉树。
完全二叉树
如果对满二叉树的结点进行编号, 约定编号从根结点起, 自上而下, 自左而右。则深度为k的, 有n个结点的二叉树, 当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时, 称之为完全二叉树。
满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树。
树的遍历
树的遍历有两个基本方法：深度优先遍历和广度优先遍历
深度优先遍历分为中序遍历、前序遍历和后序遍历
前序遍历从根节点开始，先左子树，后右子树,中序遍历先左子树，然后根节点，再右子树,后序遍历先左子树，后右子树，再根节点,每个子树内部遍历顺序也相同
广度优先算法(BFS,Breadth First Search)遍历在于层次遍历，分为自上而下和自下而上
从上到下打印二叉树
二叉树的每层最大元素
实现平衡二叉树
平衡二叉树：空树或者任何一个结点的左子树与右子树都是平衡二叉树，并且高度之差的绝对值不超过 1。
平衡因子：某节点的左子树与右子树的高度(深度)差即为该节点的平衡因子。平衡二叉树中不存在平衡因子大于 1 的节点。在一棵平衡二叉树中，节点的平衡因子只能取 0 、1 或者 -1 ，分别对应着左右子树等高，左子树比较高，右子树比较高。
平衡二叉树的失衡调整主要是通过旋转最小失衡子树来实现的。根据旋转的方向有两种处理方式，左旋 与 右旋 。
左旋/右旋
（1）节点的右/左孩子代表此节点 （2）节点的右/左孩子的左/右子树变为节点的右/左子树 （3）将此节点作为右/左孩子节点的左/右子树。
二叉搜索树（BST，binary search tree）
二叉搜索树又称二叉查找树，是一种特殊的二叉树，用于改善二叉树查找的效率。
二叉查找树的性质：
其左子树下每个后代节点的值都小于节点n的值
其右子树下每个后代节点的值都大于节点n的值
只要某一个节点不符合二叉搜索树的性质，则该二叉树不属于二叉查找树
根据二叉查找树的性质，给定任意两个节点就能够判断大小
红黑树
红黑树在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为logn
红黑树的5个性质：
1.每个节点要么是红的，要么是黑的
2.根结点是黑的
3.每个叶节点都是黑的
4.如果一个节点是红节点，那么他的两个儿子都是黑节点
3.对于任意节点而言，其到叶节点尾端的每条路径都包含相同数目的黑节点。