1. 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 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':
        pointer = root
        while pointer:
            if p.val<pointer.val and q.val<pointer.val: 
                pointer = pointer.left
            elif  p.val>pointer.val and q.val>pointer.val: 
                pointer = pointer.right
            else:return pointer
        return None

2. 剑指 Offer 68 - II. 二叉树的最近公共祖先


个人理解：
假设一个节点代表一片区域，上层区域可管理下层区域归，两个逃犯躲在其中两片区域，请找出可以覆盖两个逃犯的最小区域

  1. 对于某个区域，如果为空，直接返回空，如果刚好有一个逃犯在此区域，则假设两个逃犯都在（并不确定），直接就向上级汇报该区域
  2. 否则询问其管辖的两子个区域，如果两个子区域同时向其汇报存在逃犯，则确定两个逃犯在该区域，则直接就向上级汇报该区域
  3. 如果只有一个子区域向其汇报存在逃犯，则假设两个逃犯都在该子区域，向上级汇报该子区域
  4. 如果两个子区域都汇报不存在逃犯，则向上级汇报空

Q: 可以发现1中我们没有判断是否有两个逃犯，只要有一个逃犯就默认两个逃犯都在，直接向上级汇报，为什么不用询问子区域呢？
A: 因为上级区域会根据他所有的子区域进行判断，如果上级区域的两个子区域都反映有逃犯就证明当前区域只有一个逃犯，这时更新为这个上级区域，否则一直默认前面的假设成立，如果到最后假设还成立的话就说明假设为真

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 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:
        if not root or root in [p,q]:return root
        left = self.lowestCommonAncestor(root.left,p,q)
        right = self.lowestCommonAncestor(root.right,p,q)
        if left and right:return root
        elif left:return left
        elif right:return right
        else:return None

3. LeetCode 124. 二叉树中的最大路径和

为什么计算maxGain就可以得到最大路径和呢？

maxGain定义

某个节点的maxGain指在以这个节点为根节点的子树上，从根节点出发，任意节点结束的最大路径长度，如果为负则设为0，空节点也为0

求解maxGain方法

  1. 计算maxGain就可以用递归方法，后序遍历
  2. 先计算左右子树maxGain，再挑个大的和自身相加，再和0取最大值
  3. 代码实现
    1
    2
    3
    4
    5
    6
    def maxGain(node):
        if not node:
            return 0
        left = maxGain(node.left)
        right = maxGain(node.right)
        return max(left+node.val,right+node.val,0)

最大路径和与maxGain有什么关系？

  1. 某棵非空树的最大路径必定存在一个最高节点，对这个节点来说，最大路径和就是：左右子树的maxGain加上自身节点值
  2. 所以求某棵树的最大路径和问题转换成：求所有节点的左右子树的maxGain加上自身节点值，并返回一个最大值
  3. 这一步只要在后序遍历计算所有节点maxGain时附带算一下就行
  4. 代码实现
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, val=0, left=None, right=None):
    #         self.val = val
    #         self.left = left
    #         self.right = right

    class Solution:
        def maxPathSum(self, root: TreeNode) -> int:
            self.maxSum = float('-inf')
            def maxGain(node):
                if not node:
                    return 0
                left = maxGain(node.left)
                right = maxGain(node.right)
                self.maxSum = max(self.maxSum,left+right+node.val) # 这就是附带的一句
                return max(left+node.val,right+node.val,0)
            maxGain(root)
            return self.maxSum