08二叉树的递归套路

/ 技术相关 / 0 条评论 / 220浏览

数据结构与算法转载

原文地址

1 二叉树的递归套路

1、 可以解决面试中的绝大部分二叉树(95%以上)的问题，尤其是树形dp问题

2、 其本质是利用递归遍历二叉树的便利性，每个节点在递归的过程中可以回到该节点3次

==具体步骤为：==

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

1.1 二叉树的递归套路深度实践

1.1.1 例一：判断二叉树平衡与否

给定一棵二叉树的头结点head，返回这颗二叉树是不是平衡二叉树

平衡树概念：在一棵二叉树中，每一个子树，左树的高度和右树的高度差不超过1

那么如果以X为头的这颗树，要做到平衡，那么X的左树要是平衡的，右树也是平衡的，且X的左树高度和右树高度差不超过1

所以该题，我们X需要向左右子树要的信息为，1.高度 2. 是否平衡

package class08;

public class Code01_IsBalanced {

	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}

	public static boolean isBalanced1(Node head) {
		boolean[] ans = new boolean[1];
		ans[0] = true;
		process1(head, ans);
		return ans[0];
	}

	public static int process1(Node head, boolean[] ans) {
		if (!ans[0] || head == null) {
			return -1;
		}
		int leftHeight = process1(head.left, ans);
		int rightHeight = process1(head.right, ans);
		if (Math.abs(leftHeight - rightHeight) > 1) {
			ans[0] = false;
		}
		return Math.max(leftHeight, rightHeight) + 1;
	}

	public static boolean isBalanced2(Node head) {
		return process2(head).isBalaced;
	}

	// 左、右要求一样，Info 表示信息返回的结构体
	public static class Info {
	        // 是否平衡
		public boolean isBalaced;
		// 高度多少
		public int height;

		public Info(boolean b, int h) {
			isBalaced = b;
			height = h;
		}
	}

        // 递归调用，X自身也要返回信息Info。
        // 解决X节点(当前节点)怎么返回Info信息
	public static Info process2(Node X) {
	        // base case
		if (X == null) {
			return new Info(true, 0);
		}
		// 得到左树信息
		Info leftInfo = process2(X.left);
		// 得到右树信息
		Info rightInfo = process2(X.right);
		
		// 高度等于左右最大高度，加上当前头结点的高度1
		int height = Math.max(leftInfo.height, rightInfo.height) + 1;
		boolean isBalanced = true;
		// 左树不平衡或者右树不平衡，或者左右两子树高度差超过1
		// 那么当前节点为头的树，不平衡
		if (!leftInfo.isBalaced || !rightInfo.isBalaced || Math.abs(leftInfo.height - rightInfo.height) > 1) {
			isBalanced = false;
		}
		// 加工出当前节点的信息返回
		return new Info(isBalanced, height);
	}

	// for test
	public static Node generateRandomBST(int maxLevel, int maxValue) {
		return generate(1, maxLevel, maxValue);
	}

	// for test
	public static Node generate(int level, int maxLevel, int maxValue) {
		if (level > maxLevel || Math.random() < 0.5) {
			return null;
		}
		Node head = new Node((int) (Math.random() * maxValue));
		head.left = generate(level + 1, maxLevel, maxValue);
		head.right = generate(level + 1, maxLevel, maxValue);
		return head;
	}

	public static void main(String[] args) {
		int maxLevel = 5;
		int maxValue = 100;
		int testTimes = 1000000;
		for (int i = 0; i < testTimes; i++) {
			Node head = generateRandomBST(maxLevel, maxValue);
			if (isBalanced1(head) != isBalanced2(head)) {
				System.out.println("Oops!");
			}
		}
		System.out.println("finish!");
	}

}

1.1.2 例二：返回二叉树任意两个节点最大值

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

1、有可能最大距离和当前节点X无关，即最大距离是X左树的最大距离，或者右树的最大距离

2、最大距离跟X有关，即最大距离通过X。左树离X最远的点，到X右树上离X最远的点。即X左树的高度加上X自身高度1，加上X右树上的高度

结论：那么根据递归套路，我们每次递归，需要返回X左树的最大距离和高度，同理返回X右树的最大距离和高度。Info包含最大距离和高度

package class08;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

public class Code08_MaxDistance {

	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}

	public static int maxDistance1(Node head) {
		if (head == null) {
			return 0;
		}
		ArrayList<Node> arr = getPrelist(head);
		HashMap<Node, Node> parentMap = getParentMap(head);
		int max = 0;
		for (int i = 0; i < arr.size(); i++) {
			for (int j = i; j < arr.size(); j++) {
				max = Math.max(max, distance(parentMap, arr.get(i), arr.get(j)));
			}
		}
		return max;
	}

	public static ArrayList<Node> getPrelist(Node head) {
		ArrayList<Node> arr = new ArrayList<>();
		fillPrelist(head, arr);
		return arr;
	}

	public static void fillPrelist(Node head, ArrayList<Node> arr) {
		if (head == null) {
			return;
		}
		arr.add(head);
		fillPrelist(head.left, arr);
		fillPrelist(head.right, arr);
	}

	public static HashMap<Node, Node> getParentMap(Node head) {
		HashMap<Node, Node> map = new HashMap<>();
		map.put(head, null);
		fillParentMap(head, map);
		return map;
	}

	public static void fillParentMap(Node head, HashMap<Node, Node> parentMap) {
		if (head.left != null) {
			parentMap.put(head.left, head);
			fillParentMap(head.left, parentMap);
		}
		if (head.right != null) {
			parentMap.put(head.right, head);
			fillParentMap(head.right, parentMap);
		}
	}

	public static int distance(HashMap<Node, Node> parentMap, Node o1, Node o2) {
		HashSet<Node> o1Set = new HashSet<>();
		Node cur = o1;
		o1Set.add(cur);
		while (parentMap.get(cur) != null) {
			cur = parentMap.get(cur);
			o1Set.add(cur);
		}
		cur = o2;
		while (!o1Set.contains(cur)) {
			cur = parentMap.get(cur);
		}
		Node lowestAncestor = cur;
		cur = o1;
		int distance1 = 1;
		while (cur != lowestAncestor) {
			cur = parentMap.get(cur);
			distance1++;
		}
		cur = o2;
		int distance2 = 1;
		while (cur != lowestAncestor) {
			cur = parentMap.get(cur);
			distance2++;
		}
		return distance1 + distance2 - 1;
	}

	public static int maxDistance2(Node head) {
		return process(head).maxDistance;
	}

        // 我们的信息，整棵树的最大距离和整棵树的高度
	public static class Info {
		public int maxDistance;
		public int height;

		public Info(int dis, int h) {
			maxDistance = dis;
			height = h;
		}
	}
    
        // 以X节点为头
	public static Info process(Node X) {
	        // base case
		if (X == null) {
			return new Info(0, 0);
		}
		// 默认从左树拿到我们需要的info
		Info leftInfo = process(X.left);
		// 默认从右树拿到我们需要的info
		Info rightInfo = process(X.right);
		// 用左右树的信息，加工自身的info
		// 自身的高度是，左右较大的高度加上自身节点高度1
		int height = Math.max(leftInfo.height, rightInfo.height) + 1;
		// 自身最大距离，是左右树最大距离和左右树高度相加再加1，求最大值
		int maxDistance = Math.max(
				Math.max(leftInfo.maxDistance, rightInfo.maxDistance),
				leftInfo.height + rightInfo.height + 1);
		// 自身的info返回
		return new Info(maxDistance, height);
	}

	// for test
	public static Node generateRandomBST(int maxLevel, int maxValue) {
		return generate(1, maxLevel, maxValue);
	}

	// for test
	public static Node generate(int level, int maxLevel, int maxValue) {
		if (level > maxLevel || Math.random() < 0.5) {
			return null;
		}
		Node head = new Node((int) (Math.random() * maxValue));
		head.left = generate(level + 1, maxLevel, maxValue);
		head.right = generate(level + 1, maxLevel, maxValue);
		return head;
	}

	public static void main(String[] args) {
		int maxLevel = 4;
		int maxValue = 100;
		int testTimes = 1000000;
		for (int i = 0; i < testTimes; i++) {
			Node head = generateRandomBST(maxLevel, maxValue);
			if (maxDistance1(head) != maxDistance2(head)) {
				System.out.println("Oops!");
			}
		}
		System.out.println("finish!");
	}

}

1.1.3 例三：返回二叉树中的最大二叉搜索树Size

给定一颗二叉树的头结点head，返回这颗二叉树中最大的二叉搜索树的Size

搜索二叉树概念：整颗树上没有重复值，左树的值都比我小，右树的值都比我大。每颗子树都如此。

递归套路。1、与当前节点X无关，即最终找到的搜索二叉树，不以X为头

2、与X有关，那么X的左树整体是搜索二叉树，右树同理，且左树的最大值小于X,右树的最小值大于X

package class08;

import java.util.ArrayList;

public class Code04_MaxSubBSTSize {

	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}

	public static int getBSTSize(Node head) {
		if (head == null) {
			return 0;
		}
		ArrayList<Node> arr = new ArrayList<>();
		in(head, arr);
		for (int i = 1; i < arr.size(); i++) {
			if (arr.get(i).value <= arr.get(i - 1).value) {
				return 0;
			}
		}
		return arr.size();
	}

	public static void in(Node head, ArrayList<Node> arr) {
		if (head == null) {
			return;
		}
		in(head.left, arr);
		arr.add(head);
		in(head.right, arr);
	}

	public static int maxSubBSTSize1(Node head) {
		if (head == null) {
			return 0;
		}
		int h = getBSTSize(head);
		if (h != 0) {
			return h;
		}
		return Math.max(maxSubBSTSize1(head.left), maxSubBSTSize1(head.right));
	}

	public static int maxSubBSTSize2(Node head) {
		if (head == null) {
			return 0;
		}
		return process(head).maxSubBSTSize;
	}

//	public static Info process(Node head) {
//		if (head == null) {
//			return null;
//		}
//		Info leftInfo = process(head.left);
//		Info rightInfo = process(head.right);
//		int min = head.value;
//		int max = head.value;
//		int maxSubBSTSize = 0;
//		if (leftInfo != null) {
//			min = Math.min(min, leftInfo.min);
//			max = Math.max(max, leftInfo.max);
//			maxSubBSTSize = Math.max(maxSubBSTSize, leftInfo.maxSubBSTSize);
//		}
//		if (rightInfo != null) {
//			min = Math.min(min, rightInfo.min);
//			max = Math.max(max, rightInfo.max);
//			maxSubBSTSize = Math.max(maxSubBSTSize, rightInfo.maxSubBSTSize);
//		}
//		boolean isBST = false;
//		if ((leftInfo == null ? true : (leftInfo.isAllBST && leftInfo.max < head.value))
//				&& (rightInfo == null ? true : (rightInfo.isAllBST && rightInfo.min > head.value))) {
//			isBST = true;
//			maxSubBSTSize = (leftInfo == null ? 0 : leftInfo.maxSubBSTSize)
//					+ (rightInfo == null ? 0 : rightInfo.maxSubBSTSize) + 1;
//		}
//		return new Info(isBST, maxSubBSTSize, min, max);
//	}

	// 任何子树,都返回4个信息
	public static class Info {
	        // 整体是否是二叉搜索树
		public boolean isAllBST;
		// 最大的满足二叉搜索树树条件的size
		public int maxSubBSTSize;
		// 整棵树的最小值
		public int min;
		// 整棵树的最大值
		public int max;

		public Info(boolean is, int size, int mi, int ma) {
			isAllBST = is;
			maxSubBSTSize = size;
			min = mi;
			max = ma;
		}
	}

        // 以X为头
	public static Info process(Node X) {
	        // base case
		if(X == null) {
			return null;
		}
		// 默认左树可以给我info信息
		Info leftInfo = process(X.left);
		// 默认右树可以给我info信息
		Info rightInfo = process(X.right);

                // 通过左右树给我的信息，加工我自己的info

		int min = X.value;
		int max = X.value;
		
		// 左树不为空，加工min和max
		if(leftInfo != null) {
			min = Math.min(min, leftInfo.min);
			max = Math.max(max, leftInfo.max);
		}
		// 右树不为空，加工min和max
		if(rightInfo != null) {
			min = Math.min(min, rightInfo.min);
			max = Math.max(max, rightInfo.max);
		}

                // 可能性1与X无关的情况
		int maxSubBSTSize = 0;
		if(leftInfo != null) {
			maxSubBSTSize = leftInfo.maxSubBSTSize;
		}
		if(rightInfo !=null) {
			maxSubBSTSize = Math.max(maxSubBSTSize, rightInfo.maxSubBSTSize);
		}
		
		// 可能性2，与X有关
		boolean isAllBST = false;

		if(
				// 左树和人右树整体需要是搜索二叉树
				(  leftInfo == null ? true : leftInfo.isAllBST    )
				&&
				(  rightInfo == null ? true : rightInfo.isAllBST    )
				&&
				// 左树最大值<X，右树最小值>X
				(leftInfo == null ? true : leftInfo.max < X.value)
				&&
				(rightInfo == null ? true : rightInfo.min > X.value)
				
				
				) {
			
			maxSubBSTSize = 
					(leftInfo == null ? 0 : leftInfo.maxSubBSTSize)
					+
					(rightInfo == null ? 0 : rightInfo.maxSubBSTSize)
					+
					1;
					isAllBST = true;
			
			
		}

		return new Info(isAllBST, maxSubBSTSize, min, max);
	}
	
	// for test
	public static Node generateRandomBST(int maxLevel, int maxValue) {
		return generate(1, maxLevel, maxValue);
	}

	// for test
	public static Node generate(int level, int maxLevel, int maxValue) {
		if (level > maxLevel || Math.random() < 0.5) {
			return null;
		}
		Node head = new Node((int) (Math.random() * maxValue));
		head.left = generate(level + 1, maxLevel, maxValue);
		head.right = generate(level + 1, maxLevel, maxValue);
		return head;
	}

	public static void main(String[] args) {
		int maxLevel = 4;
		int maxValue = 100;
		int testTimes = 1000000;
		for (int i = 0; i < testTimes; i++) {
			Node head = generateRandomBST(maxLevel, maxValue);
			if (maxSubBSTSize1(head) != maxSubBSTSize2(head)) {
				System.out.println("Oops!");
			}
		}
		System.out.println("finish!");
	}

}

1.1.4 例四：派对最大快乐值

排队最大快乐值问题，员工信息定义如下，多叉树结构：

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

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

现在公司要来办party，你可以决定哪些员工来，哪些员工不来，规则:

1、 如果某个员工来了，那么这个员工的所有直接下级都不能来

2、 排队的整体快乐值是所有到场员工的快乐值的累加

3、 你的目标是让排队的整体快乐值尽量的大

给定一颗多叉树头结点boss，请返回排队的最大快乐值

思路：根据X来与不来分类

如果X来，我们能获得X的快乐值X.happy。X的直接子不能来，但我们能拿到X某个子树整棵树的的最大快乐值

如果X不来，不发请柬，我们能获得X的快乐值为0，X直接子树头结点来或者不来求最大值...

package class08;

import java.util.ArrayList;
import java.util.List;

public class Code09_MaxHappy {

        // 员工对应的多叉树节点结构
	public static class Employee {
		public int happy;
		public List<Employee> nexts;

		public Employee(int h) {
			happy = h;
			nexts = new ArrayList<>();
		}

	}

	public static int maxHappy1(Employee boss) {
		if (boss == null) {
			return 0;
		}
		return process1(boss, false);
	}

	public static int process1(Employee cur, boolean up) {
		if (up) {
			int ans = 0;
			for (Employee next : cur.nexts) {
				ans += process1(next, false);
			}
			return ans;
		} else {
			int p1 = cur.happy;
			int p2 = 0;
			for (Employee next : cur.nexts) {
				p1 += process1(next, true);
				p2 += process1(next, false);
			}
			return Math.max(p1, p2);
		}
	}

	public static int maxHappy2(Employee boss) {
		if (boss == null) {
			return 0;
		}
		Info all = process2(boss);
		return Math.max(all.yes, all.no);
	}

        // 递归信息
	public static class Info {
	        // 头结点在来的情况下整棵树的最大值
		public int yes;
		// 头结点在不来的情况下整棵树的最大值
		public int no;

		public Info(int y, int n) {
			yes = y;
			no = n;
		}
	}

	public static Info process2(Employee x) {
	        // base case 基层员工
		if (x.nexts.isEmpty()) {
			return new Info(x.happy, 0);
		}
		// 当前X来的初始值
		int yes = x.happy;
		// 当前X不来的初始值
		int no = 0;
		// 每棵子树调用递归信息
		for (Employee next : x.nexts) {
			Info nextInfo = process2(next);
			// 根据子树的递归返回的信息，加工自身的info
			// 如果X来，子不来
			yes += nextInfo.no;
			// 如果X不来，子不确定来不来
			no += Math.max(nextInfo.yes, nextInfo.no);
		}
		return new Info(yes, no);
	}

	// for test
	public static Employee genarateBoss(int maxLevel, int maxNexts, int maxHappy) {
		if (Math.random() < 0.02) {
			return null;
		}
		Employee boss = new Employee((int) (Math.random() * (maxHappy + 1)));
		genarateNexts(boss, 1, maxLevel, maxNexts, maxHappy);
		return boss;
	}

	// for test
	public static void genarateNexts(Employee e, int level, int maxLevel, int maxNexts, int maxHappy) {
		if (level > maxLevel) {
			return;
		}
		int nextsSize = (int) (Math.random() * (maxNexts + 1));
		for (int i = 0; i < nextsSize; i++) {
			Employee next = new Employee((int) (Math.random() * (maxHappy + 1)));
			e.nexts.add(next);
			genarateNexts(next, level + 1, maxLevel, maxNexts, maxHappy);
		}
	}

	public static void main(String[] args) {
		int maxLevel = 4;
		int maxNexts = 7;
		int maxHappy = 100;
		int testTimes = 100000;
		for (int i = 0; i < testTimes; i++) {
			Employee boss = genarateBoss(maxLevel, maxNexts, maxHappy);
			if (maxHappy1(boss) != maxHappy2(boss)) {
				System.out.println("Oops!");
			}
		}
		System.out.println("finish!");
	}

}

1.1.5 例五：判断二叉树是否是满二叉树

给定一棵二叉树的头结点head，返回这颗二叉树是不是满二叉树。

思路：满二叉树一定满足2^L - 1 == N，其中L是这颗二叉树的高度，N是这颗二叉树的节点个数

package class08;

public class Code02_IsFull {

	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}

	public static boolean isFull1(Node head) {
		if (head == null) {
			return true;
		}
		int height = h(head);
		int nodes = n(head);
		return (1 << height) - 1 == nodes;
	}

	public static int h(Node head) {
		if (head == null) {
			return 0;
		}
		return Math.max(h(head.left), h(head.right)) + 1;
	}

	public static int n(Node head) {
		if (head == null) {
			return 0;
		}
		return n(head.left) + n(head.right) + 1;
	}

	public static boolean isFull2(Node head) {
		if (head == null) {
			return true;
		}
		// 如果满足公式是满二叉树
		Info all = process(head);
		return (1 << all.height) - 1 == all.nodes;
	}

    // 信息
	public static class Info {
		public int height;
		public int nodes;

		public Info(int h, int n) {
			height = h;
			nodes = n;
		}
	}

    // 递归套路
	public static Info process(Node head) {
		if (head == null) {
			return new Info(0, 0);
		}
		Info leftInfo = process(head.left);
		Info rightInfo = process(head.right);
		// 高度
		int height = Math.max(leftInfo.height, rightInfo.height) + 1;
		// 节点数
		int nodes = leftInfo.nodes + rightInfo.nodes + 1;
		return new Info(height, nodes);
	}

	// for test
	public static Node generateRandomBST(int maxLevel, int maxValue) {
		return generate(1, maxLevel, maxValue);
	}

	// for test
	public static Node generate(int level, int maxLevel, int maxValue) {
		if (level > maxLevel || Math.random() < 0.5) {
			return null;
		}
		Node head = new Node((int) (Math.random() * maxValue));
		head.left = generate(level + 1, maxLevel, maxValue);
		head.right = generate(level + 1, maxLevel, maxValue);
		return head;
	}

	public static void main(String[] args) {
		int maxLevel = 5;
		int maxValue = 100;
		int testTimes = 1000000;
		for (int i = 0; i < testTimes; i++) {
			Node head = generateRandomBST(maxLevel, maxValue);
			if (isFull1(head) != isFull2(head)) {
				System.out.println("Oops!");
			}
		}
		System.out.println("finish!");
	}

}

1.1.6 例六：二叉搜索树的头结点

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

和前文的返回二叉搜索子树的Size问题类似

package class08;

import java.util.ArrayList;

public class Code05_MaxSubBSTHead {

	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}

	public static int getBSTSize(Node head) {
		if (head == null) {
			return 0;
		}
		ArrayList<Node> arr = new ArrayList<>();
		in(head, arr);
		for (int i = 1; i < arr.size(); i++) {
			if (arr.get(i).value <= arr.get(i - 1).value) {
				return 0;
			}
		}
		return arr.size();
	}

	public static void in(Node head, ArrayList<Node> arr) {
		if (head == null) {
			return;
		}
		in(head.left, arr);
		arr.add(head);
		in(head.right, arr);
	}

	public static Node maxSubBSTHead1(Node head) {
		if (head == null) {
			return null;
		}
		if (getBSTSize(head) != 0) {
			return head;
		}
		Node leftAns = maxSubBSTHead1(head.left);
		Node rightAns = maxSubBSTHead1(head.right);
		return getBSTSize(leftAns) >= getBSTSize(rightAns) ? leftAns : rightAns;
	}

	public static Node maxSubBSTHead2(Node head) {
		if (head == null) {
			return null;
		}
		return process(head).maxSubBSTHead;
	}

	// 每一棵子树Info
	public static class Info {
		public Node maxSubBSTHead;
		public int maxSubBSTSize;
		public int min;
		public int max;

		public Info(Node h, int size, int mi, int ma) {
			maxSubBSTHead = h;
			maxSubBSTSize = size;
			min = mi;
			max = ma;
		}
	}

	public static Info process(Node X) {
		if (X == null) {
			return null;
		}
		Info leftInfo = process(X.left);
		Info rightInfo = process(X.right);
		int min = X.value;
		int max = X.value;
		Node maxSubBSTHead = null;
		int maxSubBSTSize = 0;
		if (leftInfo != null) {
			min = Math.min(min, leftInfo.min);
			max = Math.max(max, leftInfo.max);
			maxSubBSTHead = leftInfo.maxSubBSTHead;
			maxSubBSTSize = leftInfo.maxSubBSTSize;
		}
		if (rightInfo != null) {
			min = Math.min(min, rightInfo.min);
			max = Math.max(max, rightInfo.max);
			if (rightInfo.maxSubBSTSize > maxSubBSTSize) {
				maxSubBSTHead = rightInfo.maxSubBSTHead;
				maxSubBSTSize = rightInfo.maxSubBSTSize;
			}
		}
		if ((leftInfo == null ? true : (leftInfo.maxSubBSTHead == X.left && leftInfo.max < X.value))
				&& (rightInfo == null ? true : (rightInfo.maxSubBSTHead == X.right && rightInfo.min > X.value))) {
			maxSubBSTHead = X;
			maxSubBSTSize = (leftInfo == null ? 0 : leftInfo.maxSubBSTSize)
					+ (rightInfo == null ? 0 : rightInfo.maxSubBSTSize) + 1;
		}
		return new Info(maxSubBSTHead, maxSubBSTSize, min, max);
	}

	// for test
	public static Node generateRandomBST(int maxLevel, int maxValue) {
		return generate(1, maxLevel, maxValue);
	}

	// for test
	public static Node generate(int level, int maxLevel, int maxValue) {
		if (level > maxLevel || Math.random() < 0.5) {
			return null;
		}
		Node head = new Node((int) (Math.random() * maxValue));
		head.left = generate(level + 1, maxLevel, maxValue);
		head.right = generate(level + 1, maxLevel, maxValue);
		return head;
	}

	public static void main(String[] args) {
		int maxLevel = 4;
		int maxValue = 100;
		int testTimes = 1000000;
		for (int i = 0; i < testTimes; i++) {
			Node head = generateRandomBST(maxLevel, maxValue);
			if (maxSubBSTHead1(head) != maxSubBSTHead2(head)) {
				System.out.println("Oops!");
			}
		}
		System.out.println("finish!");
	}

}

1.1.7 例子七：是否是完全二叉树

给定一棵二叉树的头结点head，返回这颗二叉树是不是完全二叉树

完全二叉树概念在堆的章节，有介绍。

宽度优先遍历解决思路:

1、如果用树的宽度优先遍历的话，如果某个节点有右孩子，但是没有左孩子，一定不是完全二叉树

2、在1条件的基础上，一旦遇到第一个左右孩子不双全的节点，后续所有节点必须为叶子节点

二叉树递归套路解法思路：

1、满二叉树（无缺口），一定是完全二叉树。此时左右树需要给X的信息是，是否是满的和高度。如果左右树满，且左右树高度一样，那么是该种情况--满二叉树

2、有缺口，1缺口可能停在我的左树上。左树需要给我是否是完全二叉树，右树需要给X是否是满二叉树，且左树高度比右树高度大1

3、缺口可能在左右树的分界。左树是满的，右树也是满的，左树高度比右树大1

4、左树已经满了，缺口可能在我的右树上。左树是满的，右树是完全二叉树，且左右树高度一样

==所以我们的递归时，需要向子树要的信息为：是否是完全二叉树，是否是满二叉树，高度==

package class08;

import java.util.LinkedList;

public class Code06_IsCBT {

	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}

    // 宽度优先遍历解决方法
	public static boolean isCBT1(Node head) {
		if (head == null) {
			return true;
		}
		LinkedList<Node> queue = new LinkedList<>();
		// 是否遇到过左右两个孩子不双全的节点
		boolean leaf = false;
		Node l = null;
		Node r = null;
		queue.add(head);
		while (!queue.isEmpty()) {
			head = queue.poll();
			l = head.left;
			r = head.right;
			if (
			// 如果遇到了不双全的节点之后，又发现当前节点不是叶节点
			(leaf && (l != null || r != null)) || (l == null && r != null)

			) {
				return false;
			}
			if (l != null) {
				queue.add(l);
			}
			if (r != null) {
				queue.add(r);
			}
			if (l == null || r == null) {
				leaf = true;
			}
		}
		return true;
	}

    // 递归的解法
	public static boolean isCBT2(Node head) {
		if (head == null) {
			return true;
		}
		return process(head).isCBT;
	}

	// 对每一棵子树，是否是满二叉树、是否是完全二叉树、高度
	public static class Info {
		public boolean isFull;
		public boolean isCBT;
		public int height;

		public Info(boolean full, boolean cbt, int h) {
			isFull = full;
			isCBT = cbt;
			height = h;
		}
	}

    // 对于任何节点，我们要返回三个元素组成的Info
	public static Info process(Node X) {
	    // 如果是空树，我们封装Info而不是返回为空
	    // 方便下文不需要额外增加判空处理
		if (X == null) {
			return new Info(true, true, 0);
		}
		// 左树info
		Info leftInfo = process(X.left);
		// 右树info
		Info rightInfo = process(X.right);
		
		// 接下来整合当前X的Info
		
		// 高度信息=左右树最大高度值+1
		int height = Math.max(leftInfo.height, rightInfo.height) + 1;
		
		// X是否是满二叉树信息=左右都是满且左右高度一样
		boolean isFull = leftInfo.isFull 
				&& 
				rightInfo.isFull 
				&& leftInfo.height == rightInfo.height;
		
		// X是否是完全二叉树
		boolean isCBT = false;
		// 满二叉树是完全二叉树
		if (isFull) {
			isCBT = true;
		// 以x为头整棵树，不满
		} else { 
		    // 左右都是完全二叉树才有讨论的必要
			if (leftInfo.isCBT && rightInfo.isCBT) {
				// 第二种情况
				if (leftInfo.isCBT 
						&& rightInfo.isFull 
						&& leftInfo.height == rightInfo.height + 1) {
					isCBT = true;
				}
				// 第三种情况
				if (leftInfo.isFull 
						&& 
						rightInfo.isFull 
						&& leftInfo.height == rightInfo.height + 1) {
					isCBT = true;
				}
				// 第四种情况
				if (leftInfo.isFull 
						&& rightInfo.isCBT && leftInfo.height == rightInfo.height) {
					isCBT = true;
				}
				
			}
		}
		return new Info(isFull, isCBT, height);
	}

	// for test
	public static Node generateRandomBST(int maxLevel, int maxValue) {
		return generate(1, maxLevel, maxValue);
	}

	// for test
	public static Node generate(int level, int maxLevel, int maxValue) {
		if (level > maxLevel || Math.random() < 0.5) {
			return null;
		}
		Node head = new Node((int) (Math.random() * maxValue));
		head.left = generate(level + 1, maxLevel, maxValue);
		head.right = generate(level + 1, maxLevel, maxValue);
		return head;
	}

	public static void main(String[] args) {
		int maxLevel = 5;
		int maxValue = 100;
		int testTimes = 1000000;
		for (int i = 0; i < testTimes; i++) {
			Node head = generateRandomBST(maxLevel, maxValue);
			if (isCBT1(head) != isCBT2(head)) {
				System.out.println("Oops!");
			}
		}
		System.out.println("finish!");
	}

}

1.1.8 例子八：最低公共祖先

给次那个一颗二叉树的头结点head，和另外两个节点a和b。返回a和b的最低公共祖先

二叉树的最低公共祖先概念： 任意两个节点，往父亲看，最开始交汇的节点，就是最低公共祖先

解法一：用辅助map，Key表示节点，Value表示节点的父亲节点。我们把两个目标节点的父亲以此放到map中，依次遍历

解法二：使用二叉树的递归套路。

1、o1和o2都不在以X为头的树上

2、o1和o2有一个在以X为头的树上

3、o1和o2都在以X为头的树上

3.1、X为头的树，左树右树各有一个

3.2、X为头的树，左树含有o1和o2

3.3、X为头的树，右树含有o1和o2

4、X自身就是o1或者o2，即如果X是o1那么左右树收集到o2即可，如果X是o2，左右树收集到o1即可。

package class08;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

public class Code07_lowestAncestor {

	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}
    
    // 解法1，借助辅助Map和Set
	public static Node lowestAncestor1(Node head, Node o1, Node o2) {
		if (head == null) {
			return null;
		}
		// key的父节点是value
		HashMap<Node, Node> parentMap = new HashMap<>();
		parentMap.put(head, null);
		// 递归填充map
		fillParentMap(head, parentMap);
		// 辅助set
		HashSet<Node> o1Set = new HashSet<>();
		Node cur = o1;
		o1Set.add(cur);
		// o1Set存入的是沿途所有的父节点
		while (parentMap.get(cur) != null) {
			cur = parentMap.get(cur);
			o1Set.add(cur);
		}
		cur = o2;
		// o2的某个父节点在o1Set中，就是我们要找的节点
		while (!o1Set.contains(cur)) {
			cur = parentMap.get(cur);
		}
		return cur;
	}

	public static void fillParentMap(Node head, HashMap<Node, Node> parentMap) {
		if (head.left != null) {
			parentMap.put(head.left, head);
			fillParentMap(head.left, parentMap);
		}
		if (head.right != null) {
			parentMap.put(head.right, head);
			fillParentMap(head.right, parentMap);
		}
	}

    // 解法1，二叉树递归套路解法
	public static Node lowestAncestor2(Node head, Node o1, Node o2) {
		return process(head, o1, o2).ans;
	}

	// 任何子树需要的信息结构
	public static class Info {
	    // o1和o2的最初交汇点，如果不是在当前这颗X节点的树上，返回空
		public Node ans;
		// 在当前子树上，是否发现过o1和o2
		public boolean findO1;
		public boolean findO2;

		public Info(Node a, boolean f1, boolean f2) {
			ans = a;
			findO1 = f1;
			findO2 = f2;
		}
	}

	public static Info process(Node X, Node o1, Node o2) {
	    // o1和o2不为空，那么空树上的Info如下
		if (X == null) {
			return new Info(null, false, false);
		}
		// 左树返回的Info
		Info leftInfo = process(X.left, o1, o2);
		// 右树返回的Info
		Info rightInfo = process(X.right, o1, o2);
		
		// 构建X自身需要返回的Info
		// X为头的树上是否发现了o1
		boolean findO1 = X == o1 || leftInfo.findO1 || rightInfo.findO1;
		// X为头的树上是否发现了o2
		boolean findO2 = X == o2 || leftInfo.findO2 || rightInfo.findO2;
		// 	O1和O2最初的交汇点在哪？

		// 1) 在左树上已经提前交汇了,最初交汇点保留左树的
		Node ans = null;
		if (leftInfo.ans != null) {
			ans = leftInfo.ans;
		}
		// 2) 在右树上已经提前交汇了，最初交汇点保留右树的
		if (rightInfo.ans != null) {
			ans = rightInfo.ans;
		}
		// 3) 没有在左树或者右树上提前交汇
		if (ans == null) {
		    // 但是找到了o1和o2，那么交汇点就是X自身
			if (findO1 && findO2) {
				ans = X;
			}
		}
		return new Info(ans, findO1, findO2);
	}

	// for test
	public static Node generateRandomBST(int maxLevel, int maxValue) {
		return generate(1, maxLevel, maxValue);
	}

	// for test
	public static Node generate(int level, int maxLevel, int maxValue) {
		if (level > maxLevel || Math.random() < 0.5) {
			return null;
		}
		Node head = new Node((int) (Math.random() * maxValue));
		head.left = generate(level + 1, maxLevel, maxValue);
		head.right = generate(level + 1, maxLevel, maxValue);
		return head;
	}

	// for test
	public static Node pickRandomOne(Node head) {
		if (head == null) {
			return null;
		}
		ArrayList<Node> arr = new ArrayList<>();
		fillPrelist(head, arr);
		int randomIndex = (int) (Math.random() * arr.size());
		return arr.get(randomIndex);
	}

	// for test
	public static void fillPrelist(Node head, ArrayList<Node> arr) {
		if (head == null) {
			return;
		}
		arr.add(head);
		fillPrelist(head.left, arr);
		fillPrelist(head.right, arr);
	}

	public static void main(String[] args) {
		int maxLevel = 4;
		int maxValue = 100;
		int testTimes = 1000000;
		for (int i = 0; i < testTimes; i++) {
			Node head = generateRandomBST(maxLevel, maxValue);
			Node o1 = pickRandomOne(head);
			Node o2 = pickRandomOne(head);
			if (lowestAncestor1(head, o1, o2) != lowestAncestor2(head, o1, o2)) {
				System.out.println("Oops!");
			}
		}
		System.out.println("finish!");
	}
}

==二叉树的递归套路，最终转化为基于X只找可能性即可。即树形DP问题==

本站文章除注明转载/出处外，均为作者原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为: 2022/11/02 00:34