二叉树的BFS和DFS
1. ⼆叉树的直径
leetcode 543 / lintcode 1181
描述
定义dfs(结点）
出口： 当前节点为空的时候结束
拆解：通过左右子树得到答案
返回：当前子树的最长链长度，当前子树的最长路径的长度
• 为啥？
• 假设存在C->D为树上最⻓距离，且C、D均不为点A。
• 分类讨论
• i. C->root->D :CD路径上有root。
• 那为什么不选择A->root->D呢？
• ii. C->x->D : x为C和D的LCA，且x不为root。
• 那么为什么不选A->x->D呢？
作者：Stefan_1999
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例 :
给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意：两结点之间的路径长度是以它们之间边的数目表示。
思路解题思路：
可否减少问题规模？即把大问题分解成小问题 大问题是什么，小问题又是什么？ 如何使用相同的方法去解决问题分析：
大问题是求整棵二叉树的最大直径长度， 而一棵树的直径长度可由左右子树的直径组成或取左右子树中的最大值，故问题可以转化为 以这棵树root为结点的最大直径长度 = max(以左子树为结点的最长直径长度， 以右子树为节点的最长直径长度, 左子树最长链长度+右子树最长链长度） 这里链代表连接当前结点和其左/右子树的路径（不能弯曲） 问题大小就是树的大小，而每个问题，都可以用相同的公式来得到答案，而且可以大事花小，小事化无， 所以可以用递归的方法中的分治来解决这个问题。 主函数返回 dfs(root)得到的最长链的长度 dfs 怎么写定义dfs(结点）
出口： 当前节点为空的时候结束
拆解：通过左右子树得到答案
返回：当前子树的最长链长度，当前子树的最长路径的长度
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param root: a root of binary tree
@return: return a integer
"""
def diameterOfBinaryTree(self, root):
# write your code here
max_chain, max_path = self.dfs(root)
return max_path
def dfs(self, root):
if not root:
return (0, 0)
left_max_chain, left_max_path = self.dfs(root.left)
right_max_chain, right_max_path = self.dfs(root.right)
now_max_chain = max(left_max_chain, right_max_chain) + 1
now_max_path = max(left_max_path, right_max_path, left_max_chain + right_max_chain)
return now_max_chain, now_max_path
Follow up 树上最长路径
lintcode 1469
方法1: 利用上题的方法
方法2:
• 为啥？
• 假设存在C->D为树上最⻓距离，且C、D均不为点A。
• 分类讨论
• i. C->root->D :CD路径上有root。
• 那为什么不选择A->root->D呢？
• ii. C->x->D : x为C和D的LCA，且x不为root。
• 那么为什么不选A->x->D呢？
以下是BFS的解法，参考代码
class Solution:
"""
@param n: The number of nodes
@param starts: One point of the edge
@param ends: Another point of the edge
@param lens: The length of the edge
@return: Return the length of longest path on the tree.
"""
def longestPath(self, n, starts, ends, lens):
# Write your code here
# 1. 建立无向图 buildGraph(结点个数，starts, ends, lens)
# 利用数据结构dict{0: [[1, 1], [2, 2]]} 去构建无向图
# 2. 寻找离root最远的点A：bfs(root, grpah)
# queue的条件: a. 把起始点root和当前距离为0的组合放进队列
# b. 把当前遍历的点和距离都加入queue
# visited: 由于是无向图，需要把加入queue的每个结点都+1，不然会抛MLE
# 更新条件：如果当前距离比全局最长距离要大，更新最长距离和当前结点
# 返回： 找到的从root出发的最远距离结点A，root与A的距离
# 3. 寻找离点A最远的距离点B：bfs(A, graph)
# 逻辑和上面的bfs一样，最后返回B和A与B的距离
# 返回最远距离(A->B)
graph = self.buildGraph(n, starts, ends, lens)
A, fromDist = self.bfs(0, graph)
B, toDist = self.bfs(A, graph)
return toDist
def buildGraph(self, n, starts, ends, lens):
graph = collections.defaultdict(list)
for i in range(n - 1):
graph[starts[i]].append([ends[i], lens[i]])
graph[ends[i]].append([starts[i], lens[i]])
return graph
def bfs(self, start, graph):
queue = collections.deque([[start, 0]])
#queue.append([start, 0])
maxDist = 0
visited = set([start])
while queue:
node, dist = queue.popleft()
if dist > maxDist:
maxDist = dist
farestNode = node
for nei, step in graph[node]:
if nei != node and not nei in visited:
queue.append([nei, dist + step])
visited.add(nei)
return farestNode, maxDist
思考题： 为什么这题可以用两次BFS做而上题不行？
因为这题可以被构建成一个无向图，可以轻松从一个结点到另外一个结点，而上题不行。
相关题：
LintCode 94. ⼆叉树的最⼤路径和 LintCode 475. ⼆叉树的最⼤路径和 II 2. 另⼀个树的⼦树 leetcode 572 / lintcode 1165 描述给定两个非空二叉树s和t，检查树t是否和树s的一个子树具有完全相同的结构和节点值。 s的子树是一个由s中的一个节点和该节点的后续组成的树。 树s本身也可以被视为自己的一个子树。
样例1:
给出树s:
3
/ \
4 5
/ \
1 2
给出树t:
4
/ \
1 2
返回true，因为t和s的子树具有完全相同的结构和节点值。
样例2:
给出树s:
3
/ \
4 5
/ \
1 2
/
0
给出树t:
4
/ \
1 2
返回false.
思路
方法1: 可利用二叉树的解法-分治+递归
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param s: the s' root
@param t: the t' root
@return: whether tree t has exactly the same structure and node values with a subtree of s
"""
def isSubtree(self, s, t):
# Write your code here
# 1. dfs遍历每个点
# 出口：为空的时候
# 拆解：dfs 左儿子和右儿子
# 比较：以当前结点为根，与t这棵树是否完全一致
# 返回：t是以root为根的的树的子树
# 2. Compare (判断当前结点为根的树是否与t相同)
if s is None:
return t is None
if s.val == t.val and self.compare(s, t):
return True
return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)
def compare(self, s, t):
if s is None:
return t is None
if t is None or s.val != t.val:
return False
return self.compare(s.left, t.left) and self.compare(s.right, t.right)
方法2: 前序遍历序列化成字符串+找共同子串
求两个树的前序遍历。
• 若A是B的⼦树，则A的前序遍历是B的前序遍历的⼀个⼦串。
• 这个算法的优缺点是什么？
• 优点：时间复杂度可以优化
• 缺点：若树的形状很差，使⽤了⼤量的空间
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
样例1
输入: {1,2,3,#,5,#,4}
输出: [1,3,4]
说明:
1
/ \
2 3
\ \
5 4
样例2
输入: {1,2,3}
输出: [1,3]
说明:
1
/ \
2 3
思路
BFS：
出口：队列为空的时候
拆解：先遍历左子树，后遍历右子树，每层最后一个出队的就是这一层的答案
更新： 更新当前层的答案
返回： 答案list
DFS：
出口： 为空的时候
拆解：先遍历右子树，后遍历左子树，每层第一个找到的就是答案
更新：若当前层答案为0，则插入
返回： 答案list
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param root: the root of the given tree
@return: the values of the nodes you can see ordered from top to bottom
"""
def rightSideView(self, root):
# write your code here
# 1. 定义每一行的最大值是多少（记录最右边元素）
# 2. 定义队列 -> （val, 高度)
# 3. BFS
# 不断出队
# 如果该元素高度与当前高度一样 -> 更新
# 否则append当前元素
# for 孩子
# 入队（val, 当前高度 + 1）
# 4. 输出答案
right_value = []
if not root:
return right_value
depth = -1 #当前高度
queue = collections.deque()
queue.append((root, 0))
#BFS
while queue:
now_node, now_depth = queue.popleft()
if not now_node:
continue
if depth == now_depth:
right_value[depth] = now_node.val
else:
right_value.append(now_node.val)
depth = now_depth
queue.append((now_node.left, now_depth + 1))
queue.append((now_node.right, now_depth + 1))
return right_value
相关题目
LintCode 69. ⼆叉树的层次遍历
LintCode 70. ⼆叉树的层次遍历 II
给定二叉树，返回其节点值的垂直遍历顺序。 (即逐列从上到下)。
如果两个节点在同一行和同一列中，则顺序应 从左到右。
样例1:
给出树s:
3
/ \
4 5
/ \
1 2
给出树t:
4
/ \
1 2
返回true，因为t和s的子树具有完全相同的结构和节点值。
样例2:
给出树s:
3
/ \
4 5
/ \
1 2
/
0
给出树t:
4
/ \
1 2
返回false.
思路
记录每个点的横纵坐标
• DFS or BFS?
• A. DFS
• B. BFS
• C. 都⾏
• 搜索完了，使⽤排序即可
• 那么，在都⾏的情况下，我们使⽤什么数据结构呢？
• 我们就用BFS，因为可以有下面的小优化：
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param root: the root of tree
@return: the vertical order traversal
"""
def verticalOrder(self, root):
# write your code here
# 1. 用hashmap来记录每一列的元素有哪些
# 2. bfs
# 出口: queue为空
# 更新: 每次出队将元素加入queue，把结点按左右顺序加到-1和+1的横坐标(结点，横坐标)
# 3. 答案按照列坐标排序，得到最后答案
results = collections.defaultdict(list)
queue = collections.deque()
queue.append((root, 0))
while queue:
node, x = queue.popleft()
if not node:
continue
results[x].append(node.val)
queue.append((node.left, x - 1))
queue.append((node.right, x + 1))
return [results[i] for i in sorted(results)]
Follow up:
如果两个节点在同一行和同一列中，则顺序应 从小到大。
需要在queue中保存纵坐标，横坐标，和节点，答案也要多增加一维纵坐标，然后排序，而不是等到最后结果都算晚了才去排序。
给定二叉搜索树的根结点 root，返回 L 和 R（含）之间的所有结点的值的和。
二叉搜索树保证具有唯一的值。
样例 1:
输入：root = [10,5,15,3,7,null,18], L = 7, R = 15
输出：32
样例 2:
输入：root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
输出：23
思路
分治 + 递归
BST问题：在OA中，强⾏搜O(N)也是个办法
• 找到所有的值，排序，求和得到答案
• 如何优雅的做出来？
• 考虑BST的性质：左⼦树⽐根⼩，右⼦树⽐根⼤
• 递归即可
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param root: the root node
@param L: an integer
@param R: an integer
@return: the sum
"""
def rangeSumBST(self, root, L, R):
# write your code here.
# 1. 写主函数
# return root中所有[L,R]元素之和
# 2. dfs: 参数: 当前数的根节点，L, R
# 出口: root == null
# 拆解：val
# 1. val right 防止越界
# 2. val > R -> left 防止越界
# 3. val >= L && val <= R: left, right
# 返回值：当前树中所有[L,R]元素之和
return self.dfs(root, L, R)
def dfs(self, root, L, R):
if not root:
return 0
if root.val R:
return self.dfs(root.left, L, R)
return root.val + self.dfs(root.left, L, R) + self.dfs(root.right, L, R)
6.总结: ⼆叉树中最常见的两种解题思路及模版
二叉树的题可以用分治+递归解决（占了很大部分）
dfs的时候，
定义（参数，返回值）
出口（if not root: return …)
拆解（self.dfs(root.left),self.dfs(root.right)）
二叉树的题（80%是O(N)，15%O(N^2),5%奇怪的复杂度）
什么类型用bfs好，什么类型用dfs好呢
bfs：二叉树中，按层遍历的问题
dfs：求所有路径、递归分治
二叉搜索树的形状没有特殊形状（注意与满二叉树、完全二叉树的区别）
在二叉搜索树中，我们需要尽量让时间复杂度降低到O(h)的级别。
相关问题 915
代码中应该返回什么值：当你能答案，就可以。如果得不出答案，就增加返回值的个数（维度）
类似题目：lintcode 88. LCA -> common ancestor
⼆叉树中使⽤BFS的时候：答案与层序有关。 BST —> OA中可以偷懒O(N)算法。但是后续的⾯试，考官不会让你偷懒。
模版：
def dfs(self, root):
if not root:
return
self.dfs(root.left)
self.dfs(root.right)
return ...
作者：Stefan_1999
