左神提升5：树型DP 问题

朱雀 2022-09-10 05:25 143阅读 0赞

## 树型DP ##

### 关于树型DP的套路 ###

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

写递归的过程：

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

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

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

## 543. 二叉树的直径 ##

https://leetcode-cn.com/problems/diameter-of-binary-tree/  
[点击][Link 1]

### 解题思路 ###

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

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;
            }
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/90742e737abf4fc6a78fe60f32ba26b1.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/67de07d5089049cd9501935f12d8f73a.png
[Link 1]: https://leetcode-cn.com/problems/diameter-of-binary-tree/