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总是存在的），可以转化为：

1. 判断root是否是p或者q，如果是，直接返回root为最近公共祖先
2. 否则，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)