1.解决树问题的两类思路
-
1.1先转为线性问题，然后处理
树的问题属于非线性的问题，但往往可以通过遍历一棵树将树结构转换为线性结构，如通过前中后序遍历将整棵树的结点按一定的顺序存入线性表中，实现树结构向线性结构的转换。这样一来，树问题就转化为了我们更熟悉、更容易入手的线性问题
-
1.2递归解决
树的定义就是递归的，因此树问题往往可以通过设计有效的递归算法解决
树的递归，说穿了就分为2大类：DFS深度优先搜索 和 BFS广度优先搜索。不是DFS的思路就是BFS的思路，跑不掉的。一般而言，DFS居绝大多数，基本都是前中后序遍历的一些变形；BFS更关注的则是层次顺序
如何正确地递归解决问题，是难点所在。写递归的基本思路，可以回看分段做事+返回值：双枪破递归
树问题转换为线性问题再处理，树问题通过遍历转为线性问题需要一次时间，解决线性问题又需要一次时间，虽更熟悉更利于入手，但时间复杂度也更高
递归解决，不需要经过结构转换，直接在树上进行操作，时间复杂度更优，代码更简洁，但递归也相对难想一些。简洁的代码总是有优美的思想的
下面用例子体会一下
2.例
例1.给定一个二叉树, 找到该树中两个指定节点p、q的最近公共祖先
例如，给定如下二叉树。结点6和结点0的最近公共祖先是结点3，结点6和结点7的最近公共祖先是结点5，结点6和结点5的最近公共祖先是结点5
二叉树-例
- 转换为线性问题
通过中序遍历将树转换为线性表存储，那么在线性表中，由于中序遍历的访问顺序，两个结点p、q一定分布在他们的最近公共祖先的两侧，即如同 p ancestor q 这样的分布。这样，我们就可以通过判断线性表中p q与当前root的位置关系，不断更新root，直到root满足p ancestor q 这样的分布，root即为所求的祖先
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
result = list()
self.inOrder(root, result)
p_index = result.index(p.val)
q_index = result.index(q.val)
root_index = result.index(root.val)
while True:
# 如果p q在root的左侧，更新root为root的左孩子
if (p_index < root_index and q_index < root_index):
root = root.left
root_index = result.index(root.val)
# 如果p q在root的右侧，更新root为root的右孩子
elif (p_index > root_index and q_index > root_index):
root = root.right
root_index = result.index(root.val)
else:
return root
# 中序遍历
def inOrder(self, root, result):
if not root:
return
self.inOrder(root.left, result)
result.append(root.val)
self.inOrder(root.right, result)
上面的代码中，不管三七二十一直接对整棵树进行了中序遍历，所有结点都访问了一次。但实际上，当我们访问p q之后，就不用再继续访问结点了。因此可以优化一下inOrder函数，当p q被访问后，不再访问未访问的结点。如下：
class Solution:
def __init__(self):
self.p_found = False
self.q_found = False
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
result = list()
self.inOrder(root, p , q, result)
print(result)
p_index = result.index(p.val)
q_index = result.index(q.val)
root_index = result.index(root.val)
while True:
if (p_index < root_index and q_index < root_index):
root = root.left
root_index = result.index(root.val)
elif (p_index > root_index and q_index > root_index):
root = root.right
root_index = result.index(root.val)
else:
return root
def inOrder(self, root, p, q, result):
if not root:
return
self.inOrder(root.left, p, q, result)
result.append(root.val)
# 以下判断p q是否被访问
if root == p:
self.p_found = True
if root == q:
self.q_found = True
# 如果p q在当前root的左支都被访问，则return
if self.p_found and self.q_found:
return
self.inOrder(root.right, p, q, result)
- 递归解决
树的问题，要习惯和善于从递归的角度思考和解决
DFS: 在以root.left为根结点的树中寻找p q最近公共祖先（结果记为A）+ 在以root.right为根结点的树中寻找p q最近公共祖先（结果记为B）
在以root为根结点的树中寻找p q的最近公共祖先（p、q总是存在的），可以转化为：
- 判断root是否是p或者q，如果是，直接返回root为最近公共祖先
- 否则，p和q一定在root的子树里。那么，在以root.left为根结点的树中寻找p q最近公共祖先（结果记为A） + 在以root.right为根结点的树中寻找p q最近公共祖先（结果记为B）。那么，
如果A而非B，说明p q两个结点都在root.left这边，A为最近公共祖先，返回
如果B而非A，说明p q两个结点都在root.right这边，B为最近公共祖先，返回
如果非A而非B，说明p q两个结点在root两侧都没找到，None为最近公共祖先，返回
如果A而B，说明在root两侧都找到了p q的最近公共祖先，也就是说p q两个结点分布在root两侧，root为最近公共祖先，返回
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 这个递归的方法有点6
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if root == None:
return None
if root.val == p.val or root.val == q.val:
return root
root1 = self.lowestCommonAncestor(root.left, p, q)
root2 = self.lowestCommonAncestor(root.right, p, q)
# print(root2)
if root1 and not root2:
return root1
if root2 and not root1:
return root2
if not root1 and not root2:
return None
# 剩下的情况就是root1和root2都存在，说明在root两边找到了p和q
return root
例2.给定一棵二叉树，计算它任意两个结点路径长度中的最大值。这条路径可能穿过根结点
思路：典型的DFS，遍历所有节点，对于每个节点，计算左侧的最大深度，再计算右侧的最大深度，然后相加得到经过该节点的最长路径。其中，最大深度，最长路径这些词已经直接把DFS的思路告诉得明明白白
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# 本质上是求左右子树的深度
class Solution:
def __init__(self):
self.diameter = 0
def diameterOfBinaryTree(self, root: TreeNode) -> int:
self.diameterOfBinaryTree1(root)
return self.diameter
def diameterOfBinaryTree1(self, root: TreeNode) -> int:
if not root:
return 0
if root.left:
# 计算左子树深度
l = self.diameterOfBinaryTree1(root.left) + 1
else:
l = 0
if root.right:
# 计算右子树深度
r = self.diameterOfBinaryTree1(root.right) + 1
else:
r = 0
# 宽度
print('root.val is %s, left_len is %s, right_len is %s' % (root.val, l , r))
self.diameter = max(self.diameter, l + r)
# 返回较长的一支
return max(l, r)
