一、重要说明

1、递归是一种思想，将这种思想落实到二叉树这种数据结果的相关运用上，使我更加了解递归的作用。

2、以下所举的算法例子主要都是基于后序遍历的基础上实现的，即先遍历左子树，再遍历右子树，最后访问根节点，对于每一棵树都是如此。可以认为，递归方式可以从左/右子树上收集信息，从而在根节点处进行汇总。

3、递归分为在递去的过程中解决问题以及在归来的过程中解决问题。因为我想要的信息是从底层往上给（可以是叶子节点，也可以是空节点-》结束/返回条件），所以是在归来的过程中解决问题。

4、方法论：（可以指导对问题的思考，分析如何解决问题）
（1）假设以X节点为头，假设可以向X左树和X右树要任何信息
（2）在上一步假设下，讨论以X为头结点的树，得到答案的可能性（一般分类：与X有关、与X无关）
（3）列出所有可能性后，确定到底需要向左树和右树要什么样的信息
（4）把左树信息和右树信息求全集，就是任何一棵子树都需要返回的信息S
（5）递归函数都返回S，每一棵子树都这么要求
（6）写代码时，在代码中考虑如何把左树的信息和右树的信息整合出整棵树的信息（目标是加工出信息，也就是为Info中的每一个属性进行赋值）

5、一般需要思考的问题
（1）递归一定有一个返回机制，可以在叶子节点返回（例4），可以在null处返回，需要给出其对应的返回值，如果返回值中有要素不好确定，可以直接返回null，故而后续使用中需要进行非空判断（例3）。
（2）设定改变变量的机制，会增强设计的便利性（例3），即以假定一个初始值，然后满足if的条件，即可改变变量值（分解的思想）
（3）与X有/无关的说法是为了分析问题出现的情况，真正实现的时候其实不知道有没有关，结果是需要决策出来的。

二、Examples

1、判断一棵二叉树是否是平衡树

分析：
1、假设我们需要判断的树是以X为头结点的树，分类标准其实就是与X有关，与X无关。
与X有关即，左树和右树各自平衡，需要在X处对左树与右树的高度差进行判断（高度差不能大于1）。
与X无关，即左树或者右树已经出现不平衡性，故而不需要再在X处进行判断了。
代码实现的时候不要基于与X有无关，而是基于要为返回信息赋值，怎样的情况赋怎样的值。
2、整理出应返回的信息有：子树高度、子树的平衡性。

public static class Info{
		public int height;
		public boolean isBalance;
		
		public Info(int height,boolean isBalance) {
			this.height = height;
			this.isBalance = isBalance;
		}
	}

算法实现：

public static Info process(Node head) {
		if(head == null) {//返回条件，如果子树为空
			return new Info(0,true);//高度为0，且是平衡
		}
		Info leftInfo = process(head.left);//收集左树信息
		Info rightInfo = process(head.right);//收集右树信息
		
		//开始整合出该节点需要返回的信息
		int height = 0;//设置初始高度为1
		boolean isBalance = false;//设置是不平衡，后面如果满足平衡的条件则改为true
		
		height = Math.max(leftInfo.height, rightInfo.height) + 1;
		if(leftInfo.isBalance 
				&& rightInfo.isBalance 
				&& Math.abs(leftInfo.height - rightInfo.height) <= 1) {
			isBalance = true;
		}
		return new Info(height,isBalance);
	}

2、任何两个节点之间都存在距离，返回整棵二叉树的最大距离

说明：
是最“精简”距离，即每个节点只会经历一次
分析：
1、与X无关，即两个节点之间的最大距离不通过X，则最大距离取左树与右树最大距离的最大值；与X有关最大距离则是左树高度加右树高度+1。
2、需要的每棵树都返回的信息是：子树的最大距离、子树的高度。

public static class Info{
		//最大距离
		int maxdis;
		//高度
		int height;
		public Info() {
			
		}
		public Info(int maxdis,int height) {
			this.maxdis = maxdis;
			this.height = height;
		}
	}

3、其实写代码的时候是不知道与X有无关系，需要通过max函数决策出来。假设某一层的最大距离取的是左子树或者是右子树返回的最大距离，那么就与X无关，如果取的是高度+1，就与X有关。
讨论与X有无关，只是为了将所有的可能性都列举出来。

算法实现：

public static Info FindMaxDis(Node head) {
		if(head == null) {
			return new Info(0,0);//空树的最大距离和高度都为0
		}
		
		Info leftInfo = FindMaxDis(head.left);//收集了以head为根节点左子树的信息
		Info rightInfo = FindMaxDis(head.right);//收集了以head为根节点右子树的信息
		
		//开始汇总信息，记住需要返回的信息是为了辅助上一层
		//为最终要返回的info赋值
		int height = 0;
		int maxdis = 0;
		
		height = Math.max(leftInfo.height,rightInfo.height) + 1;
		//与X有无关情况分析的代码体现
		maxdis = Math.max(
				Math.max(leftInfo.maxdis, rightInfo.maxdis)
				,leftInfo.height + rightInfo.height +1);                 
		return new Info(maxdis,height);
	}

3、二叉树中最大的二叉搜索子树的头结点的个数

概念：
BST（二叉搜索树）：左/右子树都是BST，且左树上的所有节点都比根节点小，右树上的所有节点都比根节点大。

分析：
1、与X有关：X的左树是搜索二叉树，X的右树是搜索二叉树，且X比左树中的最大值大且比右树中的最小值小。与X无关：左/右树中搜索二叉树个数的最大值。
PS：
（1）要是与X无关，所返回的信息可以先用，即为信息赋初值
（2）要是与X有关，即X节点本身需要参与决策
2、需要的信息：
最大值、最小值、是否是搜索二叉树、搜索二叉树的个数

public static class Info2{
		int max;
		int min;
		boolean is;//整体是否是二叉搜索树
		int nodes;//符合二叉搜索树要求的节点个数
		
		public Info2(int max,int min,boolean is,int nodes) {
			this.max = max;
			this.min = min;
			this.is = is;
			this.nodes = nodes;
		}
	}

算法实现：

//min max不好设置，后续自己判断是否为空
	public static Info2 search(Node head) {
		if(head == null) {
			return null;//为防止空指针异常，后续代码需要加以判断
		}
		Info2 leftInfo = search(head.left);
		Info2 rightInfo = search(head.right);
		
		int max = head.val;//head已经做了不为空的判断
		int min = head.val;
		
		if(leftInfo != null) {//因为最底层返回的Info为空，所以需要进行非空判断之后才能使用
			max = Math.max(max, leftInfo.max);
			min = Math.min(min, leftInfo.min);
		}
		if(rightInfo != null) {
			max = Math.max(max, rightInfo.max);
			min = Math.min(min, rightInfo.min);
		}
		
		int size = 0;//符合二叉搜索树的结点个数
		if(leftInfo != null) {
			size = leftInfo.nodes;//条件先用
		}
		if(rightInfo != null) {
			size = Math.max(size, rightInfo.nodes);//条件先用
		}
		
		boolean isBST = false;
		//与X有无关情况分析的代码体现
		if((leftInfo == null  ? true : leftInfo.is)
			&& (rightInfo == null ? true : rightInfo.is)
		    && (leftInfo == null ? true : leftInfo.max < head.val)
		    && (rightInfo == null ? true : rightInfo.min > head.val)){
			isBST = true;
			//因为包括X节点在内都是BST，所以所有节点的总和
			//隐含信息：如果左右子树分别都是BST，那么返回的size就是树的节点总数
			size = (leftInfo== null ? 0 :leftInfo.nodes)
					+(rightInfo== null ? 0 :rightInfo.nodes)+1;
		}
		return new Info2(max,min,isBST,size);
	}

4、派对的最大快乐值（多叉树）

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

分析：
1、给出一个员工，分为该员工来与不来的情况。如果该员工来，则收集其直接下属不来的情况。如果该员工不来，其直接下属（们）可以来也可以不来，最大快乐值是各个员工最大值之和。
员工的定义：

public static class Employee{//职员类
		public int happy;//快乐值
		public List<Employee> nexts;
		
		public Employee(int happy) {
			nexts = new ArrayList<>();
		}
	}

2、收集的信息：（各个员工该返回的信息）
该员工来时的最大快乐值、该员工不来时的最大快乐值。

public static class Info {
		int yes;//该雇员来的时候的快乐值
		int no;//该雇员不来的时候的快乐值
		
		public Info(int yes,int no) {
			this.yes = yes;
			this.no =no;
		}
	}

算法实现：

public static Info findHappy(Employee e) {
		if(e.nexts.isEmpty()) {//以基层员工作为最终返回条件，是基层员工（与之前的例子不同的地方）
			return new Info(e.happy,0);
		}
		//初值的定义
		int yes = e.happy;
		int no = 0;
		//遍历所有下级
		for(Employee emp : e.nexts) {
			//得到每个员工返回的信息
			Info info = findHappy(emp);
			yes += info.no;//上级来了，直接下级都不会来
			no += Math.max(info.yes, info.no);//上级没来，该下级可以来也可以不来
		}
		return new Info(yes,no);
	}

三、测试样例

public static void main(String[] args) {
		Node head = new Node(1);
		head.left = new Node(2);
		head.right = new Node(3);
		head.left.left = new Node(4);
		head.left.right = new Node(5);
		head.right.left = new Node(6);
		head.right.right = new Node(7);
	}