左神提升5：树型DP 问题

68 阅读 0 评论 45 点赞

我是靠谱客的博主温柔枕头，这篇文章主要介绍左神提升5：树型DP 问题，现在分享给大家，希望可以做个参考。

树型DP

关于树型DP的套路

1）从小树到大树，得到答案的可能性，
想出题目的所有可能性，左树右树的所有情况，
2）列出所有的信息 =》设计Info类
3）写递归

写递归的过程：

得到info
process使用info进行信息传递
baseCase使用null
综合leftInfo、rightInfo
加工左右信息（注意null的时候，什么时候存在）

利用递归的思想来实现dp，dp有空间换时间
在这里插入图片描述

判断是否BST：
先列条件，和套路一样
在这里插入图片描述

543. 二叉树的直径

https://leetcode-cn.com/problems/diameter-of-binary-tree/
点击

解题思路

思路：
分两种情况，经过自己的和没经过自己的。
注意本题的经典套路

1）经过自己：左边的高度和右边的高度，再把自己也加上就是当前的最大直径
2）不经过自己：左边的最大值和右边的最大值加在一起
=》综合以上来得到最大的值就是本题的答案。

代码

复制代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int diameterOfBinaryTree(TreeNode root) {
        return process(root).distance-1;
    }

public Info process(TreeNode cur) {
        if(cur == null) {
            return null;
        }
        Info leftInfo = process(cur.left);
        Info rightInfo = process(cur.right);

int height = Math.max(leftInfo == null ?0:leftInfo.height,
                        rightInfo == null ?0:rightInfo.height);

// 拿到左右两边的最大直径长度（与自己无关的）
        int lm = leftInfo == null ? 0 : leftInfo.distance;
        int rm = rightInfo == null ? 0 : rightInfo.distance;
        int distance = Math.max(lm, rm);
        // 拿到和自己有关的最大直径长度（与自己有关）
        distance = Math.max(((leftInfo == null ?0:leftInfo.height)+
                            (rightInfo == null ?0:rightInfo.height)+1)
                            ,distance);

return new Info(distance, height+1);
    }

class Info {
        public int distance;
        public int height;

Info (int a, int b) {
            distance = a;
            height = b;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int diameterOfBinaryTree(TreeNode root) {
        return process(root).distance-1;
    }

    public Info process(TreeNode cur) {
        if(cur == null) {
            return null;
        }
        Info leftInfo = process(cur.left);
        Info rightInfo = process(cur.right);

        int height = Math.max(leftInfo == null ?0:leftInfo.height,
                        rightInfo == null ?0:rightInfo.height);

        // 拿到左右两边的最大直径长度（与自己无关的）
        int lm = leftInfo == null ? 0 : leftInfo.distance;
        int rm = rightInfo == null ? 0 : rightInfo.distance;
        int distance = Math.max(lm, rm);
        // 拿到和自己有关的最大直径长度（与自己有关）
        distance = Math.max(((leftInfo == null ?0:leftInfo.height)+
                            (rightInfo == null ?0:rightInfo.height)+1)
                            ,distance);

        return new Info(distance, height+1);
    }



    class Info {
        public int distance;
        public int height;

        Info (int a, int b) {
            distance = a;
            height = b;
        }
    }
}