数据结构-树形DP

树上的动态规划，即树形DP。做树形DP一般步骤是先将树转换为有根树，然后在树上进行深搜操作，从子节点或子树中返回信息层层往上更新至根节点。

思路：小树计算完，再算父亲树。

分析可能性（先计算小树，再计算大树）
列信息全集，定下返回值结构。
编写代码的时候，默认每颗子树都给你这样的信息，然后看拿到这些子树信息后怎么加工出父的信息。
Basecase要单独考虑一下，作为最简单的情况，要给父返回啥，不至于让他干扰。

1. 给定一棵二叉树的头节点head，请返回最大搜索二叉子树的大小

假设以每个节点为头的树，求出它的最大二叉子树，答案一定在所有节点的最大二叉子树中。

第一步：列出可能性

可能来自左子树的某棵子树
可能来自右子树的某棵子树
整棵树都是，左右子树都是搜索二叉树并且左子树最大值小于该节点，右子树最小值大于该节点

第二步：收集信息

左子树最大搜索子树大小
右子树最大搜索子树大小
左子树中最大二叉搜索子树的头部（通过查看这个头部是否等于节点的左孩子，来判断整个左子树是否都是二叉搜索树）
4、右子树最大二叉搜索子树的头部
5、左子树最大值
6、右子树最小值

因此不管对于左子树还是右子树都需要收集的信息：

最大搜索子树大小
最大搜索子树的头部
这棵树的最大值
这棵树的最小值

第三步：改递归
先假设左和右都给我这样的信息了，然后怎么利用左边和右边的信息，组出来我该返回的信息。

对于某节点，如果其左子树返回的头结点是该节点的左孩子，且其右子树返回的头结点是该节点的右孩子，且左子树的最大值小于该节点值，且右子树的最小值大于该节点值，则以该节点为根的整棵子树是二叉搜索树，长度是左长+1+右长。
如果1不成立，则判断左搜和右搜的大小，以该节点为根的最大二叉搜索树的大小为其中较大者。

BaseCase是当一棵树为空时，大小为0，头部为空，最小值为系统最小，最大值为系统最大。

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class returnData(object):
    def __init__(self, size, root, min, max):
        self.size = size
        self.root = root
        self.min = min
        self.max = max

class Solution(object):
    def BiggestSubBSTInTree(self, root):
        if not root:
            return 0
        res = self.process(root)
        return res.size

    def process(self, root):
        if not root:
            return returnData(0, None, float('inf'), float('-inf'))
        leftData = self.process(root.left)
        rightData = self.process(root.right)

        includeItSelf = 0
        if leftData.root == root.left and rightData.root == root.right and root.val > leftData.max and root.val < rightData.min:
            includeItSelf = leftData.size + 1 + rightData.size

        p1 = leftData.size
        p2 = rightData.size
        maxSize = max(p1, p2, includeItSelf)
        maxHead = leftData.root if p1 > p2 else rightData.root
        if maxSize == includeItSelf:
            maxHead = root

        return returnData(maxSize, maxHead, min(leftData.min, rightData.min, root.val), max(leftData.max, rightData.max, root.val))



if __name__ == '__main__':

    root = TreeNode(16)
    root.left = TreeNode(200)
    root.left.left = TreeNode(6)
    root.left.right = TreeNode(9)
    root.left.left.left = TreeNode(5)
    root.left.left.right = TreeNode(7)
    root.left.right.right = TreeNode(12)

    root.right = TreeNode(20)
    root.right.left = TreeNode(17)
    root.right.right = TreeNode(21)

    res = Solution().BiggestSubBSTInTree(root)
    print(res)

2 求二叉树中节点的最大距离

二叉树中，一个节点可以往上走和往下走，那么从节点A总能走到节点B。节点A走到节点B的距离为：A走到B最短路径上的节点个数。求一棵二叉树上的最远距离。

考虑每一个节点为根节点的情况，答案一定在其中。

第一步：列出可能性

来自左子树的最长距离
来自右子树的最长距离
经过该节点情况下的最远距离，左子树深度+1+右子树深度

第二步：收集信息

最长距离
树的深度

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class returnData(object):
    def __init__(self, maxLen, depth):
        self.maxLen = maxLen
        self.depth = depth

class Solution(object):
    def MaxDistanceInTree(self, root):
        if not root:
            return 0
        res = self.process(root)
        return res.maxLen

    def process(self, root):
        if not root:
            return returnData(0, 0)
        leftData = self.process(root.left)
        rightData = self.process(root.right)

        includeHeadDLen  = leftData.depth + 1 + rightData.depth
        maxLen = max(leftData.maxLen, rightData.maxLen, includeHeadDLen)
        depth = max(leftData.depth, rightData.depth) + 1

        return returnData(maxLen, depth)

if __name__ == '__main__':

    root = TreeNode(16)
    root.left = TreeNode(200)
    root.left.left = TreeNode(6)
    root.left.right = TreeNode(9)
    root.left.left.left = TreeNode(5)
    root.left.left.right = TreeNode(7)
    root.left.right.right = TreeNode(12)

    root.right = TreeNode(20)
    root.right.left = TreeNode(17)
    root.right.right = TreeNode(21)

    res = Solution().MaxDistanceInTree(root)
    print(res)

3 没有上司的晚会

一个公司的上下节关系是一棵多叉树，这个公司要举办晚会，你作为组织者已经摸清了大家的心理：一个员工的直接上级如果到场，这个员工肯定不会来。每个员工都有一个活跃度的值，决定谁来你会给这个员工发邀请函，怎么让舞会的气氛最活跃？返回最大的活跃值。

给定一个矩阵来表述这种关系

matrix = [[1,6],[1,5],[1,4]]

这个矩阵的含义是：
matrix[0] = {1 , 6}，表示0这个员工的直接上级为1,0这个员工自己的活跃度为6
matrix[1] = {1 , 5}，表示1这个员工的直接上级为1（他自己是这个公司的最大boss）,1这个员工自己的活跃度为5
matrix[2] = {1 , 4}，表示2这个员工的直接上级为1,2这个员工自己的活跃度为4
为了让晚会活跃度最大，应该让1不来，0和2来。最后返回活跃度为10

对于某节点 i
可能性：

i 来，活跃度就是X的活跃度+下属员工不来的活跃度总和
i 不来，活跃度就是每个下属员工来或不来中选最大的总和

我们可以定义 $ f(i, 0 / 1)$ 代表以 i 为根的子树的最优解（第二维的值为 0 代表不来的情况，1 代表来的情况）。则转移方程为（其中下面的 x 都是 i 的儿子）：）：

$f(i, 0)=\sum \max \{f(x, 1), f(x, 0)\}$（上司不来时，下属可以来，也可以不来）
$f(i, 1)=\sum f(x, 0)+a_{i}$ (上司来时，下属都不会来）

结果返回 $max(f(i, 0), f(i, 1))$。

class Node(object):
    def __init__(self, happy):
        self.happy = happy
        self.nexts = []

class returnData(object):
    def __init__(self, comeHappy, notComeHappy):
        self.comeHappy = comeHappy
        self.notComeHappy = notComeHappy

class Solution(object):
    def MaxHappy(self, root):
        if not root:
            return 0

        # 找到大Boss，后面从大Boss开始计算
        root = 0
        for i in range(len(matrix)):
            if i == matrix[i][0]:
                root = i
                break

        # 构建数据结构 Node [happy, nexts] happy表示活跃度，nexts表示它的直接下属
        Nodes = []
        for  i in range(len(matrix)):
            Nodes.append(Node(matrix[i][1]))
        Dicts = {}
        for i in range(len(matrix)):
            if matrix[i][0] == i:
                continue
            if matrix[i][0] not in Dicts:
                Dicts[matrix[i][0]] = [i]
            else:
                Dicts[matrix[i][0]].append(i)
        for i in range(len(matrix)):
            if i in Dicts:
                for j in Dicts[i]:
                    Nodes[i].nexts.append(Nodes[j])

        res = self.process(Nodes[root])
        return max(res.comeHappy, res.notComeHappy)

    def process(self, root):
        if not root:
            return returnData(0, 0)
        comeHappy = root.happy
        notComeHappy = 0
        for i in range(len(root.nexts)):
            data = self.process(root.nexts[i])
            comeHappy += data.notComeHappy
            notComeHappy += max(data.comeHappy, data.notComeHappy)
        return returnData(comeHappy, notComeHappy)

if __name__ == '__main__':

    matrix = [[0,16],[0,5],[0,4],[0,300],
              [1,6],[1,7],[1,9],
              [2,3],[2,7],
              [3,10],[3,2],[3,3],[3,5]]

    res = Solution().MaxHappy(matrix)
    print(res)

4 判断一棵树是否是平衡二叉树


class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class returnData(object):
    def __init__(self, isB, depth):
        self.isB = isB
        self.depth = depth

class Solution(object):
    def IsBalancedTree(self, root):
        if not root:
            return True
        return self.process(root).isB


    def process(self, root):
        if not root:
            return returnData(True, 0)
        leftData = self.process(root.left)
        if not leftData.isB:
            return returnData(False, 0)
        rightData = self.process(root.right)
        if not rightData.isB:
            return returnData(False, 0)
        if abs(leftData.depth - rightData.depth) > 1:
            return returnData(False, 0)
        return returnData(True, max(leftData.depth, rightData.depth)+1)

if __name__ == '__main__':

    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
    root.left.left.left = TreeNode(6)

    res = Solution().IsBalancedTree (root)
    print(res)
`