*重建二叉树
[中等]输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
- 递归构造：前序序列的第一个值为树的根节点，由该值可以将中序序列分割成两部分，计算左部分的长度可以截取前序中存在左子树的部分，然后递归地进行子树的构造。
- 为简化查找特定结点的复杂度，使用dict存储结点和索引对。
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def reConstructBinaryTree(self, pre, tin):
val2idx = {num:idx for idx,num in enumerate(tin)}
def helper(l1,r1,l2,r2):
if l1 > r1:
return None
root = TreeNode(pre[l1])
mid_idx = val2idx[pre[l1]]
root.left = helper(l1+1,l1+mid_idx-l2,l2,mid_idx-1)
root.right = helper(l1+mid_idx-l2+1,r1,mid_idx+1,r2)
return root
return helper(0,len(pre)-1,0,len(tin)-1)
二叉树的下一个节点
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
- 思路：
对于给定的节点：
- 如果它可以是一个父节点，根据中序遍历的规则，需要输出它右子树中的最左子节点
- 如果它不是父节点：
- 若它是它父节点的左叶子，则返回它的父节点
- 若它是右叶子，则不断向上搜索父节点，直至有一个父节点k不是k的父节点的右叶子，此时返回k的父节点。
- 如果直到根节点上述情况还不成立，有可能该节点是最后一个节点或是输入的二叉树为None，则输出None
# class TreeLinkNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# self.next = None
class Solution:
def GetNext(self, pNode):
if pNode.right:
res = pNode.right
while res.left:
res = res.left
return res
while pNode.next and pNode.next.right == pNode:
pNode = pNode.next
if pNode.next:
return pNode.next
return None
*树的子结构
[中等]输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
-
递归法，判断B是否与A具有相同子结构，用同样的顺序遍历两个树，构造dfs函数，如果顶点相等且左右子树均相等则满足条件。
class Solution: def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool: if not A or not B: return False return self.dfs(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B) def dfs(self,A,B): if not B: return True if not A: return False return A.val == B.val and self.dfs(A.left,B.left) and self.dfs(A.right,B.right)
二叉树的镜像
请完成一个函数，输入一个二叉树，该函数输出它的镜像。
例如输入：
4
/ \
2 7
/ \ / \
1 3 6 9
镜像输出：
4
/ \
7 2
/ \ / \
9 6 3 1
- 深度优先遍历，分别对左右子树进行处理，递归的中止条件为root为空或左右子树均为空。
class Solution:
def mirrorTree(self, root: TreeNode) -> TreeNode:
if not root: return None
if not root.left and not root.right:
return root
root.left,root.right = root.right,root.left
if root.left: self.mirrorTree(root.left)
if root.right:self.mirrorTree(root.right)
return root
*对称的二叉树
请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false
- 递归法
- 开始判断：根结点为None时返回真，否则判断root->left和root->right的一致性。
- 终止条件：
- 两个结点A、B都为空，一致
- 其中一个为空，不一致
- 两个都不为空且值不相等，不一致
- 否则，需要对A->left与B->right以及A->right以及B->left判断。
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
def recur(a,b):
if not a and not b:return True
if not a or not b:return False
return a.val == b.val and recur(a.left,b.right) and recur(a.right,b.left)
return recur(root.left,root.right) if root else True
- 思路二：迭代法：类似于树的BFS遍历，使用一个队列存储结点，存储顺序：A->left,B->right,A->right,B->left，这样每两个相邻的相等即满足了对称条件，当队列为空时可以判定树是对称的。
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if not root:
return True
q = []
q.append(root.left)
q.append(root.right)
while q:
A = q.pop(0)
B = q.pop(0)
#两个相邻的都为None 但队列里可能还有其他结点
if not A and not B:continue
if not A or not B:return False
if A.val != B.val: return False
else:
q.append(A.left)
q.append(B.right)
q.append(B.left)
q.append(A.right)
return True
不分行从上到下打印二叉树
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。（BFS）
class Solution:
def levelOrder(self, root: TreeNode) -> List[int]:
if not root:return []
q = []
res = []
q.append(root)
while q:
node = q.pop(0)
res.append(node.val)
if node.left:q.append(node.left)
if node.right:q.append(node.right)
return res
分行从上到下打印二叉树
Python 中使用 collections 中的双端队列 deque() ，其
popleft()方法可达到 O(1) 时间复杂度；列表 list 的pop(0)方法时间复杂度为 O(N)。
- 相较于上一题，在开始遍历当前层时需要计算队列的长度(当前层节点个数)。
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
from collections import deque
if not root:
return []
q = deque()
q.append(root)
res = []
while q:
cur_nodes = []
for _ in range(len(q)):
node = q.popleft()
cur_nodes.append(node.val)
if node.left:q.append(node.left)
if node.right:q.append(node.right)
res.append(cur_nodes)
return res
之字形打印二叉树
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
- 实质与之前相同，区别在于需要判断那一层是需要逆序的，然后对那一层的结点取[::-1]
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:return []
from collections import deque
res = []
q = deque()
q.append(root)
Forward = True
while q:
cur_vals = []
for _ in range(len(q)):
node = q.popleft()
cur_vals.append(node.val)
if node.left:q.append(node.left)
if node.right:q.append(node.right)
if len(res)%2!=0 : cur_vals = cur_vals[::-1]
res.append(cur_vals)
return res
- 法二：思路一致，借助双端队列可以高效的从两边遍历，在while判断里放两个循环依次进行正向和逆向遍历。
- 注意backward遍历时在双端队列的插入。
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:return []
from collections import deque
res = []
q = deque()
q.append(root)
Forward = True
while q:
forward_vals = []
for _ in range(len(q)):
node = q.popleft()
forward_vals.append(node.val)
if node.left:q.append(node.left)
if node.right:q.append(node.right)
res.append(forward_vals)
if not q: break
backward_vals= []
for _ in range(len(q)):
node = q.pop()
backward_vals.append(node.val)
if node.right:q.appendleft(node.right)
if node.left:q.appendleft(node.left)
res.append(backward_vals)
return res
二叉树的后序遍历序列
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树：
5
/ \
2 6
/ \
1 3
示例 1：
输入: [1,6,3,2,5]
输出: false
示例 2：
输入: [1,3,2,6,5]
输出: true
- 递归法：根据后序遍历的特点，根节点为最后，若为二叉搜索树，则左子树的值均小于根节点，右子树的值均大于根节点，以此找到第一个大于根节点的位置，划分左右子树，满足二叉搜索树的条件后，再对其左右子树的序列进行判断。
class Solution:
def verifyPostorder(self, postorder: List[int]) -> bool:
def recursive_judge(subtree):
if len(subtree) <= 1:
return True
root = subtree[-1]
#只有左子树的情况
r_idx = len(subtree)-1
for i in range(len(subtree)-1):
if subtree[i] > root:
r_idx = i
break
for i in range(r_idx+1,len(subtree)-1):
if subtree[i] < root:
return False
return recursive_judge(subtree[0:r_idx]) and recursive_judge(subtree[r_idx:-1])
return recursive_judge(postorder)
二叉树中和为某一值的路径
输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
示例: 给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:
[
[5,4,11,2],
[5,8,4,5]
]
- 回溯法- 通过线序遍历来获得所有的节点值序列，使用path存储当前路径的节点值，然后通过递归遍历其左右子树以寻找满足条件的path，将path加入到res中，然后退回上一步，弹出当前节点值，遍历其他子树。
- 注意回溯算法的流程，遍历节点的回退，path的加入(python浅拷贝的问题)
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
res,path = [],[]
def recur(root,target):
if not root:return
path.append(root.val)
target -= root.val
if target == 0 and root.left is None and root.right is None:
#因为浅拷贝的影响，不能直接插入path,否则后续path的改变会影响res
res.append(list(path))
recur(root.left,target)
recur(root.right,target)
path.pop()
recur(root,sum)
return res
*二叉搜索树转化为双向链表
[中等]输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
转化为：
- 思路：还是按着递归的解法，可以看出中序遍历与目标的顺序一致，在每个结点遍历的时候设定当前节点cur与其前驱节点pre之间的指向。(最开始时，root结点与链表头head连接)
- 通过递归无法设定1->5以及5->1的连接，需要在递归中保存下这两个结点，最后设定其连接。
- 注意：因为中序(以及后序)遍历其特殊的顺序可以这么处理，前序不存在这种处理方式(对链接的更改在遍历子树之前)。
class Solution:
def treeToDoublyList(self, root: 'Node') -> 'Node':
if not root:return None
head = Node(0)
def bfs(cur,pre):
if cur is None:
return pre
pre = bfs(cur.left,pre)
pre.right = cur
cur.left = pre
pre = cur
pre = bfs(cur.right,pre)
return pre
tail = bfs(root,head)
tail.right = head.right
head.right.left = tail
return head.right
序列化二叉树
[困难]请实现两个函数，分别用来序列化和反序列化二叉树。
示例: 你可以将以下二叉树：
1
/ \
2 3
/ \
4 5
序列化为 "[1,2,3,null,null,4,5]"
- 层次化遍历，遇到None时插入null字符串，解析字符串时也添加对null的处理即可。
from collections import deque
class Codec:
def serialize(self, root):
if not root: return "[]"
res= []
q = deque()
q.append(root)
while q:
node = q.popleft()
if not node:
res.append('null')
else:
res.append(str(node.val))
q.append(node.left)
q.append(node.right)
return '['+",".join(res)+']'
def deserialize(self, data):
if data == "[]": return
vals = data[1:-1].split(',')
idx = 1
root = TreeNode(int(vals[0]))
q = deque()
q.append(root)
while q:
node = q.popleft()
if vals[idx]!='null':
node.left = TreeNode(int(vals[idx]))
q.append(node.left)
idx += 1
if vals[idx] != 'null':
node.right = TreeNode(int(vals[idx]))
q.append(node.right)
idx += 1
return root
二叉搜索树的第 k 大节点
给定一棵二叉搜索树，请找出其中第k大的节点。
示例 1:
输入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
输出: 4
示例 2:
输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
输出: 4
- 对二叉搜索树，找第k大的元素相当于是右中左遍历法，最先遍历的元素为最大值，之后根据k值递减来进行遍历，k=0即找到了第k大的元素。
class Solution:
def kthLargest(self, root: TreeNode, k: int) -> int:
def dfs(root,k):
if not root : return k
k = dfs(root.right,k)
k = k-1
if k == 0:
self.val = root.val
return -1
k = dfs(root.left,k)
return k
dfs(root,k)
return self.val
*平衡二叉树
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
1
/ \
2 2
/ \
3 3
/ \
4 4
返回 false 。
- 思路一 - 暴力解 先序遍历 ，如果树左右子树最大深度差小于2且左右子树均为平衡二叉树，则该树为平衡二叉树。
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
def max_depth(root):
if not root:return 0
return max(max_depth(root.left),max_depth(root.right))+1
if not root:return True
return abs(max_depth(root.left)-max_depth(root.right))<2 and self.isBalanced(root.left) and self.isBalanced(root.right)
- 思路二 - 后序遍历+剪枝 ，对二叉树做后序遍历，从底至顶返回子树深度，若判定某子树不是平衡树则 “剪枝” ，直接向上返回。
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
def max_depth(root):
if not root:return 0
left = max_depth(root.left)
if left == -1: return -1
right = max_depth(root.right)
if right == -1:return -1
return max(left,right)+1 if abs(left-right)<2 else -1
return max_depth(root) != -1
leetcode 104: 二叉树最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例： 给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
- 递归计算DFS
class Solution:
def maxDepth(self, root: TreeNode) -> int:
def dfs(node):
if not node:
return 0
return max(dfs(node.left),dfs(node.right))+1
return dfs(root)
- 非递归BFS 每层遍历只要队列不为空最大长度就加一。
from collections import deque
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root:return 0
que = deque()
que.append(root)
max_len = 0
while que:
max_len += 1
for _ in range(len(que)):
node = que.popleft()
que.append(node.left) if node.left else None
que.append(node.right) if node.right else None
return max_len
leetcode 111：二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回它的最小深度 2.
- 注意有叶结点的限制，因此在递归里应判断其是不是叶结点(左右子节点都是空)
class Solution:
def minDepth(self, root: TreeNode) -> int:
def recur(root):
if not root:return 0
if root.left and root.right:
return min(recur(root.left),recur(root.right))+1
elif root.left:
return recur(root.left)+1
else:
return recur(root.right)+1
return recur(root)
leetcode 226 :翻转二叉树
翻转一棵二叉树。
4
/ \
2 7
/ \ / \
1 3 6 9
输出：
4
/ \
7 2
/ \ / \
9 6 3 1
- 思路 递归，后序遍历法
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
def recur(root):
if not root:return
root.left = recur(root.left)
root.right = recur(root.right)
root.left,root.right = root.right,root.left
return root
return recur(root)
leetcode 100: 相同的树
给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
输入: 1 1
/ \ / \
2 3 2 3
[1,2,3], [1,2,3]
输出: true
示例 2:
输入: 1 1
/ \
2 2
[1,2], [1,null,2]
输出: false
- 递归-先序遍历
class Solution:
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
def recur(root_p,root_q):
if not root_p and not root_q:return True
elif not root_p or not root_q:return False
else:
return root_p.val == root_q.val and recur(root_p.left,root_q.left) and recur(root_p.right,root_q.right)
return recur(p,q)
leetcode 404: 左叶子之和
计算给定二叉树的所有左叶子之和。
示例：
3
/ \
9 20
/ \
15 7
在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
- 思路 递归时加个flag来判定是不是做子树，满足是左子树且无子节点的即为左叶子。
class Solution:
def sumOfLeftLeaves(self, root: TreeNode) -> int:
self.val = 0
def recur(root,is_left):
if not root:return
if is_left and not root.left and not root.right:
self.val += root.val
recur(root.left,True)
recur(root.right,False)
recur(root,False)
return self.val
leetcode 257: 二叉树所有路径
给定一个二叉树，返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
示例输入:
1
/ \
2 3
\
5
输出: ["1->2->5", "1->3"]
解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
通过次数32,342提交次数51,023
- 回溯遍历 简单
class Solution:
def binaryTreePaths(self, root: TreeNode) -> List[str]:
self.res = []
self.path = []
def recur(root):
if not root:return
self.path.append(str(root.val))
if not root.left and not root.right:
self.res.append("->".join(self.path))
recur(root.left)
recur(root.right)
self.path.pop()
recur(root)
return self.res
*leetcode 437: 路径总和3
[中等]给定一个二叉树，它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
返回 3。和等于 8 的路径有:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11
- 暴力解法：双重递归，路径的总数为从根结点出发的路径个数以及从其左右子结点作为根节点的路径数之和。
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> int:
def dfs(root,target):
if not root:return 0
target -= root.val
# target=0 表明 当前路径满足条件 还要计算它的左右子树是否满足条件
return (1 if target==0 else 0) + dfs(root.left,target)+dfs(root.right,target)
if not root:return 0
return dfs(root,sum) + self.pathSum(root.left,sum)+self.pathSum(root.right,sum)
- 前缀和+递归
这道题用到了一个概念，叫前缀和。就是到达当前元素的路径上，之前所有元素的和。
如果前缀总和currSum，在节点A和节点B处相差target，则位于节点A和节点B之间的元素之和是target。
因为本题中的路径是一棵树，从根往任一节点的路径上(不走回头路)，有且仅有一条路径，因为不存在环。(如果存在环，前缀和就不能用了，需要改造算法)
抵达当前节点(即B节点)后，将前缀和累加，然后查找在前缀和上，有没有前缀和currSum-target的节点(即A节点)，存在即表示从A到B有一条路径之和满足条件的情况(前缀和的相减：从根节点到当前节点的和减去从根节点到当前节点之前的某一结点的和，即为从这一结点到当前节点的路径和)。结果加上满足前缀和currSum-target的节点的数量。然后递归进入左右子树。
左右子树遍历完成之后，回到当前层，需要把当前节点添加的前缀和去除。避免回溯之后影响上一层。因为思想是前缀和，不属于前缀的，我们就要去掉它。
前缀和相减示例：
从根节点出发检索第一条路径 5 -> 3的过程：
10： 前缀和 {10:1}
5： 当前和15，不满足条件，添加进前缀和dict里。 前缀和 {15：1，10：0}
3： 当前和18，减去target 8 结果10，在dict中2，路径数加一。
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> int:
from collections import defaultdict
self.cnt = 0
def dfs(root,target,cur_prefix_sum,prefix_sum_dict):
if not root:return 0
cur_prefix_sum += root.val
old_prefix_sum = cur_prefix_sum - target
self.cnt += prefix_sum_dict[old_prefix_sum]
prefix_sum_dict[cur_prefix_sum] += 1
dfs(root.left,target,cur_prefix_sum,prefix_sum_dict)
dfs(root.right,target,cur_prefix_sum,prefix_sum_dict)
prefix_sum_dict[cur_prefix_sum] -= 1
if not root:return 0
prefix_sum_dict = defaultdict(int)
#刚好相等的情况
prefix_sum_dict[0] = 1
dfs(root,sum,0,prefix_sum_dict)
return self.cnt
leetcode 235: 二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
说明:
所有节点的值都是唯一的。 p、q 为不同节点且均存在于给定的二叉搜索树中。
- 利用二叉搜索树的性质，两个结点
p、q的最近公共祖先一定在p、q值之间。从根节点开始遍历，如果p、q同大于或小于该节点，则遍历其右(左)结点，不满足时该节点就是最近公共祖先。- 从根节点开始遍历树
- 如果节点 p 和节点 q 都在右子树上，那么以右孩子为根节点继续 1 的操作；
- 如果节点 p 和节点 q 都在左子树上，那么以左孩子为根节点继续 1 的操作；
- 如果条件 2 和条件 3 都不成立，这就意味着我们已经找到节 p 和节点 q 的 LCA 了。
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
def recur(root,p,q):
if not root:return None
if root.val > p.val and root.val > q.val:
return recur(root.left,p,q)
elif root.val < p.val and root.val < q.val:
return recur(root.right,p,q)
else:
return root
return recur(root,p,q)
leetcode 108: 将有序数组转化为二叉搜索树
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5
- 给定排好序的数组，取其中间值作为根节点就可以构建高度平衡的二叉树，根据中间结点的定义(数组奇偶数)有不同的结果。
from math import ceil
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
def recur(nums,start,end):
if start > end:return None
mid = ceil((start+end)/2)
node = TreeNode(nums[mid])
node.left = recur(nums,start,mid-1)
node.right = recur(nums,mid+1,end)
return node
return recur(nums,0,len(nums)-1)
leetcode 144: 二叉树前序遍历
给定一个二叉树，返回它的 前序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,2,3]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
- 使用栈存储结点，在每次弹出节点后，按照先右子结点、后左子节点的顺序，保证下次弹出来的是其左子节点。
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
if not root:return []
res = []
stack = []
stack.append(root)
while stack:
node = stack.pop()
res.append(node.val)
if node.right : stack.append(node.right)
if node.left : stack.append(node.left)
return res
*leetcode 94: 二叉树的中序遍历
给定一个二叉树，返回它的 中序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,2,3]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
- 类似与上一题，同样使用栈来存储之前没有访问到的节点，
- 在对节点进行遍历时，一直往根节点的左子树遍历，中间遇到的结点即为中序的父节点，
- 当不存在左子节点时开始弹出一个结点，访问该节点然后对其右子树重复上述过程。
- 循环结束条件：当前节点为空且栈为空。
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
if not root:return []
res = []
stack = []
cur = root
while stack or cur:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
res.append(cur.val)
cur = cur.right
return res
leetcode 96: 不同的二叉搜索树
给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？
示例:
输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
- 可以用动态规划的思路来解，具体的思路可参考：参考
- 核心：长度为
n的序列的不同二叉搜索树个数$G(n)=\sum_{i=1}^nG(i-1)G(n-i)$,即以不同的中间结点拆解原序列，产生的两个序列对应的二叉搜索树的笛卡尔积。 注意边界的问题
class Solution:
def numTrees(self, n: int) -> int:
G = [0]*(n+1)
G[0],G[1] = 1,1
for i in range(2,n+1):
for j in range(1,i+1):
G[i] += G[j-1]*G[i-j]
return G[n]
*leetcode 105: 从前序和中序遍历构造二叉树
根据一棵树的前序遍历与中序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
- 递归- 依据前序遍历可以得到根节点的值，从而能对中序序列划分左右两部分，然后递归完成后续左右子树的构建。一看就会一写就跪
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if len(preorder) <= 0 :return None
root = TreeNode(preorder[0])
#获取root结点在中序的索引 分割子树
pos = inorder.index(preorder[0])
root.left = self.buildTree(preorder[1:pos+1],inorder[:pos])
root.right = self.buildTree(preorder[pos+1:],inorder[pos+1:])
return root
leetcode 98: 二叉搜索树
[中等]给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:
2
/ \
1 3
输出: true
- 思路 递归法 ： 在递归函数里加入两个参数来表明当前子树的值可取的范围(左子树上限小于根节点，右子树下限大于根节点)
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
def recur(root,lower,upper):
if not root:return True
if root.val <= lower or root.val >= upper:
return False
return recur(root.left,lower,root.val) and recur(root.right,root.val,upper)
return recur(root,float('-inf'),float('inf'))
leetcode 958:完全二叉树
给定一个二叉树，确定它是否是一个完全二叉树。
百度百科中对完全二叉树的定义如下：
若设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。（注：第 h 层可能包含 1~ 2h 个节点。）
示例 1：
输入：[1,2,3,4,5,6]
输出：true
解释：最后一层前的每一层都是满的（即，结点值为 {1} 和 {2,3} 的两层），且最后一层中的所有结点（{4,5,6}）都尽可能地向左。
- 用层级便利的方法，只要在非空结点之前出现过空结点则非完全二叉树。
class Solution:
def isCompleteTree(self, root: TreeNode) -> bool:
if not root:return True
que = []
que.append(root)
null_exist = False
while que:
node = que.pop(0)
if not node :
null_exist = True
else:
if null_exist:
return False
que.append(node.left)
que.append(node.right)
return True
leetcode 543: 二叉树的直径
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例 : 给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
-
计算规律：假设我们知道对于该节点的左儿子向下遍历经过最多的节点数 L （即以左儿子为根的子树的深度） 和其右儿子向下遍历经过最多的节点数 R （即以右儿子为根的子树的深度），那么以该节点为起点的路径经过节点数的最大值即为 L+R+1。
我们记节点 node 为起点的路径经过节点数的最大值为 $d_{node}$ ，那么二叉树的直径就是所有节点 $d_{node}$ 的最大值减一。
-
因此 这个问题就转变为求左右子树的深度和。
class Solution:
def diameterOfBinaryTree(self, root: TreeNode) -> int:
self.res = 1
def depth(root):
if not root:return 0
L = depth(root.left)
R = depth(root.right)
self.res = max(self.res,L+R+1)
return max(L,R)+1
depth(root)
return self.res-1
leetcode 222: 完全二叉树节点个数
[中等]给出一个完全二叉树，求出该树的节点个数。
说明：
完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
示例:
输入:
1
/ \
2 3
/ \ /
4 5 6
输出: 6
- 简单的层级遍历
class Solution:
def countNodes(self, root: TreeNode) -> int:
res = 0
if not root:return res
que = [root]
while que:
node = que.pop()
if node:res+=1
que.append(node.left) if node.left else None
que.append(node.right) if node.right else None
return res
leetcode 1038: 从二叉搜索树到更大和树
[中等]给出二叉 搜索 树的根节点，该二叉树的节点值各不相同，修改二叉树，使每个节点 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]
提示：
树中的节点数介于 1 和 100 之间。 每个节点的值介于 0 和 100 之间。 给定的树为二叉搜索树。
- 规律分析：有图片可以看出来，实际上该树的构建是一个右、中、左结点遍历的过程，每个结点遍历的时候需要加上之前结点的和。因此，可以用简单的递归来完成遍历并更新节点值。
- 迭代法 用栈保存结点
class Solution:
def bstToGst(self, root: TreeNode) -> TreeNode:
if not root:return None
stack = []
cur_node = root
cur_sum = 0
while stack or cur_node:
while cur_node:
stack.append(cur_node)
cur_node = cur_node.right
cur_node = stack.pop()
cur_node.val += cur_sum
cur_sum = cur_node.val
cur_node = cur_node.left
return root
- 递归 传入一个参数来储存之前的结点和
class Solution:
def bstToGst(self, root: TreeNode) -> TreeNode:
def recur(root,cur_sum):
if not root:return cur_sum
cur_sum = recur(root.right,cur_sum)
root.val += cur_sum
cur_sum = root.val
cur_sum = recur(root.left,cur_sum)
return cur_sum
recur(root,0)
return root
*leetcode 662: 二叉树最大宽度
[中等]给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。
每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。
示例 1:
输入:
1
/ \
3 2
/ \ \
5 3 9
输出: 4 解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。 示例 2:
输入:
1
/
3
/ \
5 3
输出: 2 解释: 最大值出现在树的第 3 层，宽度为 2 (5,3)。 示例 3:
输入:
1
/ \
3 2
/
5
输出: 2 解释: 最大值出现在树的第 2 层，宽度为 2 (3,2)。 示例 4:
输入:
1
/ \
3 2
/ \
5 9
/ \
6 7
输出: 8 解释: 最大值出现在树的第 4 层，宽度为 8 (6,null,null,null,null,null,null,7)。 注意: 答案在32位有符号整数的表示范围内。
- 使用队列来层次遍历该二叉树，在是送入队列时同时送入其所在的层级以及该层的索引的信息，通过层数和索引来计算该行的宽度。假设父节点在n层的索引为x，则其左子节点在层n+1的索引为2x,其右子节点在层n+1的索引为2x+1。当cur_depth不等于新弹出来的结点的层级时说明到了新的一层，遇到的为最左边的结点。
class Solution:
def widthOfBinaryTree(self, root: TreeNode) -> int:
cur_depth,left,ans = 0,0,0
queue = [(root,0,0)]
for node,depth,pos in queue:
if node:
queue.append((node.left ,depth+1,pos*2))
queue.append((node.right,depth+1,pos*2+1))
#不在同一层 更新为新的一层 且该节点为最左侧结点
#遍历其他节点位置减去当前位置来找最大的宽度
if cur_depth != depth:
cur_depth = depth
left = pos
ans = max(ans,(pos-left+1))
return ans
leetcode 199:二叉树的右视图
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例:
输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:
1 <---
/ \
2 3 <---
\ \
5 4 <---
- 层次遍历，遍历每一层时用val存储结点的值，完成该层时如果val存在则插入到结果res中。
class Solution:
def rightSideView(self, root: TreeNode) -> List[int]:
if not root:return []
res = []
que = [root]
while que:
val = None
for _ in range(len(que)):
node = que.pop(0)
val = node.val
if node.left :que.append(node.left)
if node.right:que.append(node.right)
if val:res.append(val)
return res
leetcode 129: 求根到叶子节点数字之和
给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。
例如，从根到叶子节点路径 1->2->3 代表数字 123。
计算从根到叶子节点生成的所有数字之和。
说明: 叶子节点是指没有子节点的节点。
示例 1:
输入: [1,2,3]
1
/ \
2 3
输出: 25
解释:
从根到叶子节点路径 1->2 代表数字 12.
从根到叶子节点路径 1->3 代表数字 13.
因此，数字总和 = 12 + 13 = 25.
- 回溯 前序遍历 存储路径，如果满足是叶结点就插入到列表。最后求和。
class Solution:
def sumNumbers(self, root: TreeNode) -> int:
self.res = []
self.path = []
def recur(root):
if not root:return 0
self.path.append(str(root.val))
if not root.left and not root.right:
self.res.append(int("".join(self.path)))
recur(root.left)
recur(root.right)
self.path.pop()
recur(root)
return sum(self.res)
leetcode 230: 二叉搜索树中的第 k 小的元素
给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
说明： 你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
示例 1:
输入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
输出: 1
- 中序遍历
class Solution:
def kthSmallest(self, root: TreeNode, k: int) -> int:
stack = []
while stack or root:
while root:
stack.append(root)
root = root.left
root = stack.pop()
k -= 1
if k == 0:
return root.val
root = root.right
*leetcode 236: 二叉树的最近公共祖先
[中等]给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出: 3 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。 示例 2:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出: 5 解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
- 思路一 深度优先搜索，使用left、mid、right三个变量来记录父节点与左右结点是否是p或q结点(正常情况下，当前节点为LCA时需要满足其左右子树各有一个要找的值，mid用来处理p和q为父子关系的情况),当三个变量满足有两个是1的时候当前节点就是LCA。
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
self.ans = None
def recur(root,p,q):
if not root:return False
left = recur(root.left,p,q)
right = recur(root.right,p,q)
mid = root == p or root == q
if mid + left + right >= 2:
self.ans = root
return mid or left or right
recur(root,p,q)
return self.ans
- 使用父指针迭代 使用dict存储树的父指针关系，key为当前结点，value为父节点，在满足p和q都不是dict的key值情况下遍历树构造dict，之后构造出p的父节点集合，然后q指针通过dict[q]一层层向上查找，找到满足在p的父节点集合的元素时结束。
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
parent_dict = {root:None}
stack = [root]
while p not in parent_dict or q not in parent_dict:
node = stack.pop()
if node.left:
parent_dict[node.left] = node
stack.append(node.left)
if node.right:
parent_dict[node.right] = node
stack.append(node.right)
ances_p = set()
while p:
ances_p.add(p)
p = parent_dict[p]
while q not in ances_p:
q = parent_dict[q]
return q
*leetcode 145: 二叉树的后序遍历
[中等]给定一个二叉树，返回它的 后序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [3,2,1]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
- 思路一 迭代 后序遍历的结果与逆前序遍历(根右左)结果相反，可以先做逆前序遍历，最后逆序输出
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
if not root:return []
stack = [root]
ans = []
while stack:
node = stack.pop()
ans.append(node.val)
if node.left:stack.append(node.left)
if node.right:stack.append(node.right)
return ans[::-1]
- 思路二 正经的迭代 后序遍历模板
- 使用栈来保存第一次遍历经过的结点，不同于先序遍历，需要在结点入栈时，如果不存在左子节点，当前节点转向右子结点继续入栈。当前节点为空时弹出元素并遍历。之后，需要判断栈顶结点和当前节点的关系，如果栈不为空且栈顶结点是当前节点的父节点，则需要转向栈顶结点的右子结点才行
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
res = []
stack = []
node = root
while stack or node:
while node:
stack.append(node)
#判断当前节点的左子树是否存在，若存在则持续左下行，若不存在就转向右子树
node = node.left if node.left is not None else node.right
#循环结束说明走到了叶子节点，没有左右子树了，该叶子节点即为当前栈顶元素，应该访问了
node = stack.pop()
res.append(node.val)
# （下面的stack[-1]是执行完上面那句取出栈顶元素后的栈顶元素）
#若栈不为空且当前节点是栈顶元素的左节点
if stack and stack[-1].left == node:
## 则转向遍历右节点
node = stack[-1].right
else:
# 没有左子树或右子树，强迫退栈
node = None
return res
