满满的套路！！二叉树的动态规划

痛定思痛。 2023-02-17 11:24 1阅读 0赞

如果题目是一个二叉树的题，并且需要求解的答案（涉及到左右子树结果决策的）都可以用同一个模型来做。统一理解为以x为节点的树的......。下面几个题来讲解。

### 一、判断一棵树是不是平衡树 ###

所谓平衡树就是：xoxoxxxooooxoo....自己去百度。

那么我们就要求从树的叶子节点逐层向上计算出每一节点是否符合平衡树，如果有一个不符合那么就直接false。

这里的可能性：（1）是（2）不是

我们先来看节点，一个定义树的节点，另一个定义返回类型（isBalance：当前节点是否平衡，level：树的高度）

public static class Node {
            public int value;
            public Node left;
            public Node right;
            public Node(int value){
                this.value = value;
            }
        }
    
        public static class ReturnData{
            public boolean isBalance;
            public int level;
            public ReturnData(int level,boolean isBalance){
                this.level = level;
                this.isBalance = isBalance;
            }
        }

看一下递归方法：

public static ReturnData process(Node head){
            if(head == null){
                return new ReturnData(0,true);
            }
    
            ReturnData left = process(head.left);
            ReturnData right = process(head.right);
            .......
        }

方法省略了一些代码，一会再看，process方法如果到null节点，直接返回ReturnData指定当前节点是一个平衡二叉树，高度为0，因为这个需要返回给上层节点信息。下面是获得左右节点的的ReturnData，这可以理解为一个黑盒子，假设能够取得。如果能够获取之后，我们需要判断左右节点是否是平衡的，如果是平衡的他们的高度差是否大于1，如果不大于一，当前节点的子树就是平衡的。

public static ReturnData process(Node head){
            if(head == null){
                return new ReturnData(0,true);
            }
    
            ReturnData left = process(head.left);
            if(!left.isBalance){
                return new ReturnData(-1,false);
            }
    
            ReturnData right = process(head.right);
            if(!right.isBalance){
                return new ReturnData(-1,false);
            }
    
            if(Math.abs(left.level - right.level) > 1){
                return new ReturnData(-1,false);
            }
            return new ReturnData(Math.max(left.level , right.level) + 1,true);
        }

这是完整代码，这里面只要是返回了false，就会层层返回，到最上面！主方法如下调用递归。

public static boolean getIsBalance(Node head){
            return process(head).isBalance;
        }

这里面我们需要考虑的点：

（1）有几种可能性：这里面只有节点是平衡和不是平衡比较简单。

（2）定义ReturnData：需要返回给上层哪些信息？

（3）如何根据可能性和ReturnData写黑盒？

（4）最基本的递归结束条件是啥？

### 二、获得一棵二叉树的最大值和最小值 ###

一棵普通的二叉树，如何获取他的最大值和最小值呢？我们的思路是：对于任意节点，获得左子树的最大值，再获得右子树的最大值，最后和该节点的值比较取最大，就是该子树的最大值。最小值同理

public static class Node{
            public int value;
            public Node left;
            public Node right;
            public Node(int value){
                this.value = value;
            }
        }
    
        public static class ReturnType{
            public int max;
            public int min;
            public ReturnType(int max,int min){
                this.max = max;
                this.min = min;
            }
        }

父节点需要的信息就是max和min。

public static void sayFuck(Node head){
            ReturnType returnType = fuck(head);
            System.out.println(returnType.max);
            System.out.println(returnType.min);
        }
    
        public static ReturnType fuck(Node head){
            if(head == null){
                return new ReturnType(Integer.MIN_VALUE,Integer.MAX_VALUE);
            }
            ReturnType left = fuck(head.left);
            ReturnType right = fuck(head.right);
            int resMax = Math.max(Math.max(left.max,right.max),head.value);
            int resMin = Math.min(Math.min(left.min,right.min),head.value);
            return new ReturnType(resMax,resMin);
        }

注意一下这里的base-case，return new ReturnType(Integer.MIN\_VALUE,Integer.MAX\_VALUE);这里设置当为null节点的时候返回上层不影响我们的判断。最大值取整型最小，最小值取整型最大。

### 三、求二叉树上的最远距离 ###

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

简单点，来看个图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70][]

这个图最远的就是红色节点之间的距离。

实际上可以这样想：当以x为节点的最长距离。分为以下几个可能：

（1）x节点只有左子树，那么x节点最长距离就是左孩子的最长距离+1

（2）同理只有右子树。

（3）如果有左右子树，那么拿到左右孩子的高度相加再+1。

public static class Node {
            public int value;
            public Node left;
            public Node right;
    
            public Node(int value) {
                this.value = value;
            }
        }
    
        public static class ReturnType {
            public int maxDistance;
            public int depth;
    
            public ReturnType(int maxDistance, int depth) {
                this.maxDistance = maxDistance;
                this.depth = depth;
            }
        }

depth就是树的深度，maxDistance就是最长距离。

public static ReturnType process(Node node) {
            if (node == null) {
                return new ReturnType(0, 0);
            }
    
            ReturnType left = process(node.left);
            ReturnType right = process(node.right);
            //黑盒
            int includeHeadDistance = left.depth + 1 + right.depth;
            int leftDistance = left.maxDistance;
            int rightDistance = right.maxDistance;
            int resultDistance = Math.max(Math.max(leftDistance, rightDistance), includeHeadDistance);
            int depth = Math.max(left.depth, right.depth) + 1;
            return new ReturnType(resultDistance, depth);
        }

这里面如果遇到null节点，直接都是0，返回，然后计算最长距离：int resultDistance = Math.max(Math.max(leftDistance, rightDistance), includeHeadDistance);。

### 四、求一棵树的最大二叉搜索树的大小 ###

这棵树不一定是二叉搜索树，但是子树可能会有二叉搜索树。

以x为头的整棵树的最大二叉子树，这里有几个情况：

（1）来源于左子树（信息是左子树的）

（2）来源于右子树（信息是右子树的）

（3）左右子树都是搜索二叉树，他本身就是二叉搜索树（左子树的最大二叉搜索树的头节点是左孩子，右子树的最大二叉受所属的头节点是右孩子）

如何来判断一棵树是不是二叉搜索树？（1）中序递增（2）对于每一个节点的左子树的最大值比当前x节点小，右子树的最小值比当前节点大。

所以我们需要以下几个信息：搜索树的大小、搜索树的头部、左子树的最大值，右子树的最小值。

public static class Node {
            public int value;
            public Node left;
            public Node right;
    
            public Node(int value) {
                this.value = value;
            }
        }
    
        public static class ReturnType {
            public int size;
            public Node head;
            public int max;
            public int min;
    
            public ReturnType(int size, Node head, int max, int min) {
                this.size = size;
                this.head = head;
                this.max = max;
                this.min = min;
            }
        }

然后还是获取左右子树的信息，然后拆黑盒。

public static ReturnType process(Node node) {
            if (node == null) {
                new ReturnType(0,null,Integer.MIN_VALUE,Integer.MAX_VALUE);
            }
            ReturnType left = process(node.left);
            ReturnType right = process(node.right);
            //拆黑盒过程：
            int selfSize = 0;
            //如果是情况（3）
            if (left.head == node.left && right.head == node.right
                    && left.max < node.value && right.min > node.value) {
                selfSize = left.size + 1 + right.size;
            }
            //情况（1）、（2）
            Node maxNode = left.size > right.size ? left.head : right.head;
            int maxSize = Math.max(Math.max(right.size, left.size), selfSize);
    
            //情况（3）直接换头节点
            if (maxSize == selfSize) {
                maxNode = node;
            }
    
            return new ReturnType(maxSize,maxNode,
                    Math.max(Math.max(left.max,right.max),node.value),
                    Math.min(Math.min(left.min,right.min),node.value));
        }

### 五、聚会活跃度 ###

一个公司的上下节关系是一棵多叉树，这个公司要举办晚会，你作为组织者已经摸清了大家的心理：一个员工的直

接上级如果到场，这个员工肯定不会来。每个员工都有一个活跃度的值，决定谁来你会给这个员工发邀请函，怎么

让舞会的气氛最活跃？返回最大的活跃值。

举例：

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

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

看图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 1][]

实际上就是一个多叉树，上层节点就是节点的领导。直接题意，当前节点x：

（1）x来参加聚会：那么下层节点一定不会来。

（2）x不来参加聚会，下层节点可以来可以不来。

求最大活跃度：以x节点当前来或者不来的最大活跃度。所以：

public static class Node {
            public int activeNum;
    //下层节点
            public List<Node> nexts;
    
            public Node(int activeNum) {
                this.activeNum = activeNum;
                this.nexts = new ArrayList<>();
            }
        }
    
        public static class ReturnType {
    //来的活跃度
            public int comeNum;
    //不来的活跃度
            public int noComeNum;
    
            public ReturnType(int comeNum, int noComeNum) {
                this.comeNum = comeNum;
                this.noComeNum = noComeNum;
            }
        }

如果已经计算完头节点的ReturnType，直接比较两个大小返回就行：

public static int getMaxActiveNum(Node head) {
            ReturnType returnType = process(head);
            return Math.max(returnType.comeNum, returnType.noComeNum);
        }

public static ReturnType process(Node node) {
            if(node == null){
                return new ReturnType(0,0);
            }
            int comeNum = node.activeNum;
            int noComeNum = 0;
    
            for (int i = 0; i < node.nexts.size(); i++) {
                Node next = node.nexts.get(i);
                ReturnType nextData = process(next);
                //当前节点到，后代节点不可以来
                comeNum += nextData.noComeNum;
                //当前节点不来，后代节点可以来，可以不来。
                noComeNum += Math.max(nextData.comeNum, nextData.noComeNum);
            }
            return new ReturnType(comeNum, noComeNum);
        }

comeNum表示该节点来的时候，那么再循环中下面节点是一定不来的。noComeNum表示不来，那么取下面节点来或者不来的最大值。然后封装信息，返回。

这种方法的时候需要构建树结构。

下面是动态规划写法：

public static int maxHappy(int[][] matrix) {
    		int[][] dp = new int[matrix.length][2];
    		boolean[] visited = new boolean[matrix.length];
    		int root = 0;
    		for (int i = 0; i < matrix.length; i++) {
    			if (i == matrix[i][0]) {
    				root = i;
    			}
    		}
    		process(matrix, dp, visited, root);
    		return Math.max(dp[root][0], dp[root][1]);
    	}
    
    	public static void process(int[][] matrix, int[][] dp, boolean[] visited, int root) {
    		visited[root] = true;
    		dp[root][1] = matrix[root][1];
    		for (int i = 0; i < matrix.length; i++) {
    			if (matrix[i][0] == root && !visited[i]) {
    				process(matrix, dp, visited, i);
    				dp[root][1] += dp[i][0];
    				dp[root][0] += Math.max(dp[i][1], dp[i][0]);
    			}
    		}
    	}
    
    	public static void main(String[] args) {
    		int[][] matrix = { { 1, 8 }, { 1, 9 }, { 1, 10 } };
    		System.out.println(maxHappy(matrix));
    	}

实际上跟上面分析是一样的。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200613220806941.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2020061322320133.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70