二叉树的递归套路应用

ゝ一纸荒年。 2024-04-08 10:25 15阅读 0赞

## 二叉树的递归套路 ##

> 相信刷过算法题目的人都知道被DP支配的恐惧，今天我就来介绍一下如何解决二叉树里面的DP  
> 该技巧本质是利用遍历二叉树的便利性

### 1 递归套路 ###

1.  假设以X节点为头，假设可以向X的左树和X右树要任何信息
2.  在上一步的假设下，讨论以X为头节点的树，得到答案的可能性（最重要）
3.  列出所有可能性后，确定到底需要向左树和右树要什么样的信息（Info类的属性）
4.  把左树和右树信息求全集，就是任何一颗子树都需要返回的信息S
5.  递归函数都返回S，每一棵子树都这么要求
6.  写代码，在代码中考虑如何把左树的信息和右树信息整合出整棵树的信息

### 2 递归套路实践（null若不好设置交给上游） ###

#### 2.1 最大二叉搜索树子树的大小 ####

> 给定一颗二叉树的头节点head，返回这颗二叉树中最大的二叉搜索子树的大小

思路：  
①最大子树在node的左边【不过node】  
②最大子树在node的右边【不过node】  
③最大子树包含node【过node】

##### 2.1.1 定义信息收集类及节点类 #####

//节点结构
    public static class TreeNode {
        
        private TreeNode left;
        private TreeNode right;
        private int value;
    
        public TreeNode(int value) {
        
            this.value = value;
        }
    }
    
    //定义信息收集类
    public static class Info {
        
        private int maxBSTSubtreeSize;
        private int allSize;
        private int max;
        private int min;
    
        public Info(int maxBSTSubtree, int allSize, int max, int min) {
        
            //最大BST子树节点数
            this.maxBSTSubtreeSize = maxBSTSubtree;
            //总节点数
            this.allSize = allSize;
            this.max = max;
            this.min = min;
        }
    }

##### 2.1.2 定义求解方法 #####

//获取最大BST大小
    public static int largestBSTSubtree(TreeNode head) {
        
        if (head == null) {
        
            return 0;
        }
        return process(head).maxBSTSubtreeSize;
    }

##### 2.1.3 定义process处理方法 #####

//处理方法
    public static Info process(TreeNode node) {
        
        if (node == null) {
        
            //无法确定为null时，如何返回Info（max、min不好设置），因此交给上游判断
            return null;
        }
        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right);
        int max = node.value;
        int min = node.value;
        int allSize = 1;//node节点自己
        if (leftInfo != null) {
        
            max = Math.max(max, leftInfo.max);
            min = Math.min(min, leftInfo.min);
            allSize += leftInfo.allSize;
        }
        if (rightInfo != null) {
        
            max = Math.max(max, rightInfo.max);
            min = Math.min(min, rightInfo.min);
            allSize += rightInfo.allSize;
        }
        //设置左边
        int p1 = -1;
        if (leftInfo != null) {
        
            //左边最大
            p1 = leftInfo.maxBSTSubtreeSize;
        }
        //设置右边
        int p2 = -1;
        if (rightInfo != null) {
        
            p2 = rightInfo.maxBSTSubtreeSize;
        }
        //判断左树是否是平衡树
        boolean leftBST = leftInfo == null ? true : (leftInfo.maxBSTSubtreeSize == leftInfo.allSize);
        //判断右树
        boolean rightBST = rightInfo == null ? true : (rightInfo.maxBSTSubtreeSize == rightInfo.allSize);
        //如果左右都是平衡树，判断以node为头，是否是平衡树
        int p3 = -1;
        if (leftBST && rightBST) {
        
            //左边最大值小于node
            boolean leftLessNode = leftInfo == null ? true : (leftInfo.max < node.value);
            //右边最小值大于node
            boolean rightMoreNode = rightInfo == null ? true : (rightInfo.min > node.value);
            if (leftLessNode && rightMoreNode) {
        
                //node为头是BST【注意null判断】
                int leftSize = leftInfo == null ? 0 : leftInfo.allSize;
                int rightSize = rightInfo == null ? 0 : rightInfo.allSize;
                p3 = leftSize + rightSize + 1;
            }
        }
        return new Info(Math.max(p1, Math.max(p2, p3)), allSize, max, min);
    }

##### 2.1.4 全部代码 #####

//返回最大BST树大小【节点个数】
    public class MaxBSTSubTree {
        
    
    
        //节点结构
        public static class TreeNode {
        
            private TreeNode left;
            private TreeNode right;
            private int value;
    
            public TreeNode(int value) {
        
                this.value = value;
            }
        }
    
        //定义信息收集类
        public static class Info {
        
            private int maxBSTSubtreeSize;
            private int allSize;
            private int max;
            private int min;
    
            public Info(int maxBSTSubtree, int allSize, int max, int min) {
        
                //最大BST子树节点数
                this.maxBSTSubtreeSize = maxBSTSubtree;
                //总节点数
                this.allSize = allSize;
                this.max = max;
                this.min = min;
            }
        }
    
        //获取最大BST大小
        public static int largestBSTSubtree(TreeNode head) {
        
            if (head == null) {
        
                return 0;
            }
            return process(head).maxBSTSubtreeSize;
        }
    
        //处理方法
        public static Info process(TreeNode node) {
        
            if (node == null) {
        
                //无法确定为null时，如何返回Info（max、min不好设置），因此交给上游判断
                return null;
            }
            Info leftInfo = process(node.left);
            Info rightInfo = process(node.right);
            int max = node.value;
            int min = node.value;
            int allSize = 1;//node节点自己
            if (leftInfo != null) {
        
                max = Math.max(max, leftInfo.max);
                min = Math.min(min, leftInfo.min);
                allSize += leftInfo.allSize;
            }
            if (rightInfo != null) {
        
                max = Math.max(max, rightInfo.max);
                min = Math.min(min, rightInfo.min);
                allSize += rightInfo.allSize;
            }
            //设置左边
            int p1 = -1;
            if (leftInfo != null) {
        
                //左边最大
                p1 = leftInfo.maxBSTSubtreeSize;
            }
            //设置右边
            int p2 = -1;
            if (rightInfo != null) {
        
                p2 = rightInfo.maxBSTSubtreeSize;
            }
            //判断左树是否是平衡树
            boolean leftBST = leftInfo == null ? true : (leftInfo.maxBSTSubtreeSize == leftInfo.allSize);
            //判断右树
            boolean rightBST = rightInfo == null ? true : (rightInfo.maxBSTSubtreeSize == rightInfo.allSize);
            //如果左右都是平衡树，判断以node为头，是否是平衡树
            int p3 = -1;
            if (leftBST && rightBST) {
        
                //左边最大值小于node
                boolean leftLessNode = leftInfo == null ? true : (leftInfo.max < node.value);
                //右边最小值大于node
                boolean rightMoreNode = rightInfo == null ? true : (rightInfo.min > node.value);
                if (leftLessNode && rightMoreNode) {
        
                    //node为头是BST【注意null判断】
                    int leftSize = leftInfo == null ? 0 : leftInfo.allSize;
                    int rightSize = rightInfo == null ? 0 : rightInfo.allSize;
                    p3 = leftSize + rightSize + 1;
                }
            }
            return new Info(Math.max(p1, Math.max(p2, p3)), allSize, max, min);
        }
    }

#### 2.2 整棵二叉树的最大距离 ####

> 给定一颗二叉树的头节点head，任何两个节点之间都存在距离，返回整棵二叉树的最大距离

##### 2.2.1 节点及信息收集类 #####

public static class Node {
        
        private Node left;
        private Node right;
        private int value;
    
        public Node(int value){
        
            this.value = value;
        }
    }
    
    //定义信息收集类
    public static class Info{
        
        private int maxDistance;
        private int height;
    
        public Info(int maxDistance, int height){
        
            this.maxDistance = maxDistance;
            this.height = height;
        }
    }

##### 2.2.2 定义求解方法 #####

//定义处理方法
    public static int maxDistance2(Node head){
        
        if(head == null){
        
            return 0;
        }
        return process(head).maxDistance;
    }

##### 2.2.3 定义处理方法 #####

//定义处理方法
    public static Info process(Node node){
        
        if(node == null){
        
            //该题为null好设置
            return new Info(0, 0);
        }
        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right);
        //node的高度
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        //最大距离在左边【不经过node】
        int p1 = leftInfo.maxDistance;
        //最大距离在右边
        int p2 = rightInfo.maxDistance;
        //最大距离过node【左边高度，右边高度，加上自身】
        int p3 = leftInfo.height + rightInfo.height + 1;
        int maxDistance = Math.max(p1, Math.max(p2, p3));
        return new Info(maxDistance, height);
    }

##### 2.2.4 全部代码 #####

//最大距离
    public class MaxDistanceDemo {
        
    
        public static class Node {
        
            private Node left;
            private Node right;
            private int value;
    
            public Node(int value){
        
                this.value = value;
            }
        }
    
        //定义信息收集类
        public static class Info{
        
            private int maxDistance;
            private int height;
    
            public Info(int maxDistance, int height){
        
                this.maxDistance = maxDistance;
                this.height = height;
            }
        }
    
        //定义处理方法
        public static int maxDistance2(Node head){
        
            if(head == null){
        
                return 0;
            }
            return process(head).maxDistance;
        }
    
        //定义处理方法
        public static Info process(Node node){
        
            if(node == null){
        
                //该题为null好设置
                return new Info(0, 0);
            }
            Info leftInfo = process(node.left);
            Info rightInfo = process(node.right);
            //node的高度
            int height = Math.max(leftInfo.height, rightInfo.height) + 1;
            //最大距离在左边【不经过node】
            int p1 = leftInfo.maxDistance;
            //最大距离在右边
            int p2 = rightInfo.maxDistance;
            //最大距离过node【左边高度，右边高度，加上自身】
            int p3 = leftInfo.height + rightInfo.height + 1;
            int maxDistance = Math.max(p1, Math.max(p2, p3));
            return new Info(maxDistance, height);
        }
    }

#### 2.3 判断是否是完全二叉树 ####

##### 2.3.1 节点及信息收集类 #####

public static class TreeNode {
        
        private TreeNode left;
        private TreeNode right;
        private int value;
    
        public TreeNode(int value){
        
            this.value = value;
        }
    }
    
    //信息收集类
    public static class Info{
        
        //是否是满二叉树
        private boolean isFull;
        //是否是完全二叉树
        private boolean isCBT;
        //高度
        private int height;
    
        public Info(boolean isFull, boolean isCBT, int height){
        
            this.isFull = isFull;
            this.isCBT = isCBT;
            this.height = height;
        }
    }

##### 2.3.2 求解方法 #####

public static boolean isCompleteTree2(TreeNode head){
        
        return process(head).isCBT;
    }

##### 2.3.3 定义处理类 #####

public static Info process(TreeNode node){
        
        if(node == null){
        
            //null好设置
            return new Info(true, true, 0);
        }
        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right);
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        boolean isFull = leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height;
        //先设置为false【看满足四种情况的哪一个】
        boolean isCBT = false;
        if(leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height){
        
            //都是满的【高一样】
            isCBT = true;
        } else if(leftInfo.isCBT && rightInfo.isFull && leftInfo.height == rightInfo.height + 1){
        
            //左是完全【左更高】
            isCBT = true;
        } else if(leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height + 1){
        
            //左右都是满的【左更高】
            isCBT = true;
        } else if(leftInfo.isFull && rightInfo.isCBT && leftInfo.height == rightInfo.height){
        
            //左是满的，右是完全的【高度一样】
            isCBT = true;
        }
        return new Info(isFull, isCBT, height);
    }

##### 2.3.4 全部代码 #####

//判断是否是完全二叉树【递归解法】
    public class CBTDemo {
        
    
    
        public static class TreeNode {
        
            private TreeNode left;
            private TreeNode right;
            private int value;
    
            public TreeNode(int value){
        
                this.value = value;
            }
        }
    
        //信息收集类
        public static class Info{
        
            //是否是满二叉树
            private boolean isFull;
            //是否是完全二叉树
            private boolean isCBT;
            //高度
            private int height;
    
            public Info(boolean isFull, boolean isCBT, int height){
        
                this.isFull = isFull;
                this.isCBT = isCBT;
                this.height = height;
            }
        }
    
        public static boolean isCompleteTree2(TreeNode head){
        
            return process(head).isCBT;
        }
    
        public static Info process(TreeNode node){
        
            if(node == null){
        
                //null好设置
                return new Info(true, true, 0);
            }
            Info leftInfo = process(node.left);
            Info rightInfo = process(node.right);
            int height = Math.max(leftInfo.height, rightInfo.height) + 1;
            boolean isFull = leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height;
            //先设置为false【看满足四种情况的哪一个】
            boolean isCBT = false;
            if(leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height){
        
                //都是满的【高一样】
                isCBT = true;
            } else if(leftInfo.isCBT && rightInfo.isFull && leftInfo.height == rightInfo.height + 1){
        
                //左是完全【左更高】
                isCBT = true;
            } else if(leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height + 1){
        
                //左右都是满的【左更高】
                isCBT = true;
            } else if(leftInfo.isFull && rightInfo.isCBT && leftInfo.height == rightInfo.height){
        
                //左是满的，右是完全的【高度一样】
                isCBT = true;
            }
            return new Info(isFull, isCBT, height);
        }
    }

#### 2.4 拓展（沿用二叉树的递归解决其他问题） ####

题目：派对的最大快乐值

员工信息定义如下：

class Employee {
        
    	public int happy;//这名员工可以带来的快乐值
    	List<Employee> subordinates;//这名员工有哪些直接下级【注意：直接下级】
    }

公司的每个员工都符合Employee类的描述。整个公司的人员结构可以看成是一棵标准的、没有环的多叉树。树的头节点是公司唯一的老板。除老板以外的每个员工都有唯一的直接上级。叶节点是没有任何下属的基层员工（subordinates为空），除基层员工以外，每个员工都有一个或多个直接下级。

问题：  
这个公司现在要举办派对，你可以决定哪些员工来，哪些员工不来，规则：  
1.如果某个员工来了，那么这个员工所有"直接"下级都不能来  
2.排队的整体快乐之是所有当场员工快乐值得累加  
3.你的目的是让派对得整体快乐值尽量大  
给定一棵多叉树的头节点boss，请返回派对的最大快乐值

##### 2.4.1 思路 #####

本题依然可以用二叉树的递归套路求解，定义信息收集Info类（两个属性：no， yes）

##### 2.4.2 Employee结构 #####

public static class Employee {
        
        public int happy;
        //该员工的直接下属
        public List<Employee> nexts;
    
        public Employee(int happy){
        
            this.happy = happy;
            nexts = new ArrayList<>();
        }
    }

##### 2.4.3 定义信息收集类Info #####

public static class Info {
        
    	//该员工不来时，能够获取到的最大快乐值
    	private int no;
    	//该员工来时，获得的最大快乐值
    	private int yes;
    }

##### 2.4.4 定义求解方法maxHappy(Employee e) #####

public static int maxHappy2(Employee head){
        
        Info info = process(head);
        return Math.max(info.no, info.yes);
    }

##### 2.4.5 定义process处理方法 #####

public static Info process(Employee employee){
        
    	if(employee == null){
        
    		return new Info(0, 0);
    	}
    	//该员工不来：收集到的快乐值为0
    	int no = 0;
    	//员工来：收集到的快乐值为本身
    	int yes = employee.happy;
    	for(Employee e : employee.nexts){
        
    		//每个员工收集上来的信息
    		Info info = process(e);
    		//该员工不来，其下属可来可不来【取最大值】
    		no += Math.max(info.no, info.yes);
    		yes += info.yes;
    	}
    	return new Info(no, yes);
    }

##### 2.4.6 全部代码 #####

public class MaxHappyDemo {
        
    
        public static class Employee {
        
            public int happy;
            public List<Employee> nexts;
    
            public Employee(int happy){
        
                this.happy = happy;
                nexts = new ArrayList<>();
            }
        }
        public static class Info{
        
            public int no;
            public int yes;
    
            public Info(int no, int yes){
        
                this.no = no;
                this.yes = yes;
            }
        }
    
        public static int maxHappy2(Employee head){
        
            Info info = process(head);
            return Math.max(info.no, info.yes);
        }
    
        public static Info process(Employee employee){
        
            if(employee == null){
        
                return new Info(0, 0);
            }
            int no = 0;
            int yes = employee.happy;
            for(Employee e : employee.nexts){
        
                   Info nextInfo = process(e);
                   no += Math.max(nextInfo.no, nextInfo.yes);
                   yes += nextInfo.no;
            }
            return new Info(no, yes);
        }
    }