二叉树的递归套路
- 可以解决面试中绝大多数的二叉树问题尤其是树型dp问题。
- 本质是利用递归遍历二叉树的便利性。
1）假设以X节点为头，假设可以向X左树和X右树要任何信息。
2）在上一步的假设下，讨论以X为头节点的树，得到答案的可能性（最重要）。
3）列出所有可能性后，确定到底需要向左树和右树要什么样的信息。
4）把左树信息和右树信息求全集，就是任何一棵子树都需要返回的信息S。
5）递归函数都返回S，每一棵子树都这么要求。
6）写代码，在代码中考虑如何把左树的信息和右树信息整合出整棵树的信息。
练习
给定一棵二叉树的头节点head，返回这颗二叉树是不是平衡二叉树
class Solution {
class Info{
boolean balance;
int h;
public Info(boolean balance,int h){
this.balance = balance;
this.h = h;
}
}
public boolean isBalanced(TreeNode root) {
return process(root).balance;
}
private Info process(TreeNode head){
if(head == null){
return new Info(true,0);
}
Info leftInfo = process(head.left);
Info rightInfo = process(head.right);
int h = Math.max(leftInfo.h,rightInfo.h)+1;
boolean isBalanced = false;
if(leftInfo.balance && rightInfo.balance && (Math.abs(rightInfo.h - leftInfo.h))<=1){
isBalanced = true;
}
return new Info(isBalanced,h);
}
}
给定一棵二叉树的头节点head，返回这颗二叉树是不是搜索二叉树
public class SearchBinaryTree {
public static boolean isSearchBinaryTree(Node head){
if(head == null){
return true;
}
return process(head).isSearchTree;
}
private static Info process(Node node){
if(node == null){
return null;
}
Info left = process(node.left);
Info right = process(node.right);
// 最小值和最大值
int max = node.value;
int min = node.value;
if(left != null){
max = Math.max(max,left.max);
min = Math.min(min,left.min);
}
if(right != null){
max = Math.max(max,right.max);
min = Math.min(min,right.min);
}
// 左树右树是否是搜索二叉树
boolean isSearchTree = false;
if((left == null ? true : left.isSearchTree && left.max < node.value)
&& (right == null ? true : right.isSearchTree && right.min > node.value)){
isSearchTree = true;
}
return new Info(isSearchTree,max,min);
}
static class Info{
boolean isSearchTree;
int max;
int min;
public Info(boolean isSearchTree,int max,int min){
this.isSearchTree = isSearchTree;
this.max = max;
this.min = min;
}
}
}
给定一棵二叉树的头节点head，返回这颗二叉树中最大的二叉搜索子树的大小
public class SubSearchBinaryTreeSize {
public static int subSearchBinaryTreeSize(Node head){
if(head == null){
return 0;
}
return process(head).size;
}
private static Info process(Node node){
if(node == null){
return null;
}
Info left = process(node.left);
Info right = process(node.right);
int size = 0;
int max = node.value;
int min = node.value;
// 左树不为空是不是二叉树搜索树
if(left != null){
max = Math.max(max,left.max);
min = Math.min(min,left.min);
}
if(right != null){
max = Math.max(max,right.max);
min = Math.min(min,right.min);
}
boolean isSearchBinaryTree = false;
if((left == null ? true : left.isSearchBinaryTree && left.max < node.value)
&& (right == null ? true : right.isSearchBinaryTree && right.min > node.value)){
isSearchBinaryTree = true;
size = (left == null ? 0 : left.size) + (right == null ? 0 :right.size) + 1;
}else{
if(left != null){
size = Math.max(size,left.size);
}
if(right != null){
size = Math.max(size,right.size);
}
}
return new Info(size,isSearchBinaryTree,max,min);
}
static class Info{
// 以X为头结点的树 的最大搜索子树的大小
public int size;
public boolean isSearchBinaryTree;
public int max;
public int min;
public Info(int size,boolean isSearchBinaryTree,int max,int min){
this.size = size;
this.isSearchBinaryTree = isSearchBinaryTree;
this.max = max;
this.min = min;
}
}
}
给定一棵二叉树的头节点head，返回这颗二叉树中最大的二叉搜索子树的头节点.
public class SubSearchBinaryTreeHead {
public static Node subSearchBinaryTreeHead(Node head){
if(head == null){
return null;
}
return process(head).head;
}
private static Info process(Node node){
if(node == null){
return null;
}
Info left = process(node.left);
Info right = process(node.right);
int size = 0;
int max = node.value;
int min = node.value;
// 左树不为空是不是二叉树搜索树
if(left != null){
max = Math.max(max,left.max);
min = Math.min(min,left.min);
}
if(right != null){
max = Math.max(max,right.max);
min = Math.min(min,right.min);
}
Node head = null;
boolean isSearchBinaryTree = false;
if((left == null ? true : left.isSearchBinaryTree && left.max < node.value)
&& (right == null ? true : right.isSearchBinaryTree && right.min > node.value)){
// 如果是二叉搜索树，则最大为此时的头结点
isSearchBinaryTree = true;
size = (left == null ? 0 : left.size) + (right == null ? 0 :right.size) + 1;
head = node;
}else{
// 以当前节点为头的不是二叉搜索树
// 则看左右树谁打
if(left != null){
size = Math.max(size,left.size);
head = left.head;
}
if(right != null){
if(right.size > size){
head = right.head;
}
size = Math.max(size,right.size);
}
// if(left != null && right != null){
// head = left.size > right.size ? left.head : right.head;
// }
// if(left == null && right != null){
// head = right.head;
// }
// if(right == null && left != null){
// head = left.head;
// }
}
return new Info(size,isSearchBinaryTree,max,min,head);
}
static class Info{
// 以X为头结点的树 的最大搜索子树的大小
public int size;
public boolean isSearchBinaryTree;
public int max;
public int min;
public Node head;
public Info(int size,boolean isSearchBinaryTree,int max,int min,Node head){
this.size = size;
this.isSearchBinaryTree = isSearchBinaryTree;
this.max = max;
this.min = min;
this.head = head;
}
}
}
判断一个树是否是满二叉树
/**
* 主要一点 满二叉树满足 2^L -1 == n (L为树的高度，n是树的节点个数)
*/
public class FullBinaryTree {
public static boolean isFullBinaryTree(Node head){
if(head == null){
return true;
}
Info res = process(head);
return ((1 << res.height) - 1) == res.num;
}
private static Info process(Node node){
if(node == null){
return new Info(0,0);
}
Info left = process(node.left);
Info right = process(node.right);
int height = Math.max(left.height,right.height) + 1;
int num = left.num + right.num + 1;
return new Info(num,height);
}
static class Info{
public int num;
public int height;
public Info(int num,int height){
this.num = num;
this.height = height;
}
}
}
是否为完全二叉树
/**
* 递归
* 1.左右子树都是满二叉树，且高度相等
* 2.左子树是完全二叉树，右子树是满二叉树，且左子树高度=右子树高度+1
* 3.左子树是一颗满二叉树，右子树也是满二叉树，且左子树高度=右子树+1
* 4.左子树是一颗满二叉树，右子树是一颗完全二叉树，且左右子树高度相等
*
*
* 非递归
*1.若有右子树，但是无左子树，则一定不是
*2.若到某个节点后没有右子树，那么往后的所有节点都是叶子节点
*/
public class CompleteBinaryTree {
public static boolean isCompleteBinaryTree(Node head){
if(head == null){
return true;
}
return process(head).isCompleteBinaryTree;
}
private static Info process(Node node){
if(node == null){
return new Info(true,true,0);
}
Info left = process(node.left);
Info right = process(node.right);
int height = Math.max(left.height,right.height) + 1;
// 是否是满二叉树,左边是否为满二叉，右边是否为满二叉树，高度是否相等。
boolean isFull = left.isFull && right.isFull && left.height == right.height;
boolean isCompleteBinaryTree = false;
if(isFull){
// 如果是一颗满二叉树，则一定是完全二叉树
isCompleteBinaryTree = true;
}else{
if(left.isCompleteBinaryTree && right.isFull && (left.height == right.height + 1)){
isCompleteBinaryTree = true;
}
if(left.isFull && right.isFull && (left.height == right.height + 1)){
isCompleteBinaryTree = true;
}
if(left.isFull && right.isCompleteBinaryTree && (left.height == right.height)){
isCompleteBinaryTree = true;
}
}
return new Info(isCompleteBinaryTree,isFull,height);
}
static class Info{
// 是否是完全二叉树
public boolean isCompleteBinaryTree;
// 是否是满二叉树
public boolean isFull;
// 高度
public int height;
public Info(boolean isCompleteBinaryTree,boolean isFull,int height){
this.isCompleteBinaryTree = isCompleteBinaryTree;
this.isFull = isFull;
this.height = 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 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 class MaxDistance {
/**
*
* 1.与x有关,则最大距离为左子树的高度加上右子树的高度 + 1；
* 2.与x无关，则为左子树的最大距离，右子树的最大距离，中最大的一个，
* 3.取1.2中最大值，则为以往前节点为头节点的树的最大距离
*
*/
public static int maxDistance(Node head){
if(head == null){
return 0;
}
return process(head).max;
}
private static Info process(Node node){
if(node == null){
return new Info(0,0);
}
Info left = process(node.left);
Info right = process(node.right);
int height = Math.max(left.height,right.height) + 1;
int max = 0;
// 与当前节点有关
max = left.height + right.height + 1;
// 与当前节点无关
max = Math.max(Math.max(max,left.max),right.max);
return new Info(height,max);
}
static class Info{
// 以X为头的🌲的高度
public int height;
// 以X为头的最大距离
public int max;
public Info(int height,int max){
this.height = height;
this.max = max;
}
}
}
最大快乐值
public class hh {
/**
*1.当前节点来参加，则以当前节点为头的多叉树的快乐值为，当前节点的快乐值加上他其余下级不来时的快乐值总和
*2.当前节点不来，则，快乐值等于，每个下级来或不来时，快乐值最大的那一种的总和
*3.因此需要的信息有，X来时的最大快乐值，x不来时的最大快乐值
*/
public static int maxHappy(Employee boss){
if(boss == null){
return 0;
}
Info process = process(boss);
return Math.max(process.no,process.yes);
}
private static Info process(Employee employee){
if(employee == null){
// 没有这个员工
// 则来或不来都不会有快乐值
return new Info(0,0);
}
// 多叉树循环求每个子树的信息，再搜集信息，汇总
List<Employee> subordinates = employee.nexts;
int yes = employee.happy;
int no = 0;
if(subordinates != null){
for (Employee item : subordinates){
Info process = process(item);
// 当前员工来
yes += process.no;
no += Math.max(process.no,process.yes);
}
}
return new Info(yes,no);
}
static class Info{
// 来的快乐值
public int yes;
// 不来的快乐值
public int no;
public Info(int yes,int no){
this.yes = yes;
this.no = no;
}
}
}
最低公共祖先
public class MinNode {
public static Node minCommonAncestor(Node head,Node node1,Node node2){
if(head == null){
return null;
}
return process(head,node1,node2).node;
}
private static Info process(Node node,Node node1,Node node2){
if(node == null){
// 如果当前节点为空节点
return new Info(null,false,false);
}
Info left = process(node.left, node1, node2);
Info right = process(node.right, node1, node2);
// 以当前节点为头的子树有没有包含node1
boolean isNode1 = node1 == node || left.isNode1 || right.isNode1;
boolean isNode2 = node2 == node || left.isNode2 || right.isNode2;
// 最低公共祖先是哪个节点，
Node temp = null;
if(left.node != null){
temp = left.node;
}
if(right.node != null){
temp = right.node;
}
if(temp == null && isNode1 && isNode2){
temp = node;
}
return new Info(temp,isNode1,isNode2);
}
static class Info{
// 当前节点
public Node node;
// 当前节点左树上有没有发现公共祖先
public boolean isNode1;
// 当前节点右树上有没有发现公共祖先
public boolean isNode2;
public Info(Node node,boolean isNode1,boolean isNode2){
this.node = node;
this.isNode1 = isNode1;
this.isNode2 = isNode2;
}
}
}
