给定一个二叉树,判断是否是平衡二叉树

如果左子树是平衡二叉树,并且右子树是平衡二叉树,并且两子树高度差不大于1,则当前子树是平衡二叉树。

二叉树递归:

1、 定义信息体;
2、 确定basecase返回的信息;
3、 左右子节点递归收集信息;
4、 根据子节点信息,计算并返回自己的信息;

 

/**
 * 给定一个二叉树,判断是否是平衡二叉树
 */
public class TreeRecursion01 {
   
     

    public static boolean isBalance(Node head) {
   
     
        Info info = process(head);
        return info.isBalance;
    }

    private static Info process(Node node) {
   
     
        // 1、base case: 空树,高度为0,是平衡
        if (node == null) {
   
     
            Info info = new Info();
            info.isBalance = true;
            info.height = 0;
            return info;
        }

        // 2、左右递归收集信息
        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right);

        // 3、根据子信息,计算自己的信息
        Info info = new Info();
        //如果左子树是平衡二叉树,并且右子树是平衡二叉树,并且两子树高度差不大于1,则当前子树也是平衡二叉树
        if (leftInfo.isBalance && rightInfo.isBalance && Math.abs(leftInfo.height - rightInfo.height) <= 1) {
   
     
            info.isBalance = true;
        }

        //取左右子树中高度较大的加一,作为当前子树的高度
        info.height = Math.max(leftInfo.height, rightInfo.height) + 1;

        return info;
    }

    private static class Info {
   
     
        private boolean isBalance; //是否平衡
        private int height; //高度
    }

    private static class Node {
   
     
        private int value;
        private Node left;
        private Node right;
    }

}

给定一个二叉树,返回二叉树任意节点中最大的距离

 
三种可能性:

  • 左树的最大节点距离是整棵树的最大距离
  • 右树的最大节点距离是整棵树的最大距离
  • 经过头节点的最大节点距离(左树高+右树高+1),是整棵树的最大距离

所以需要信息:

  • 树高
  • 树的最大节点距离

 

/**
 * 给定一个二叉树,返回二叉树任意节点中最大的距离
 */
public class TreeRecursion02 {
   
     

    public static int findMaxDistance(Node head) {
   
     
        Info info = process(head);
        return info.maxDistance;
    }

    private static Info process(Node node) {
   
     
        // base case:空树
        if (node == null) {
   
     
            Info info = new Info();
            info.height = 0;
            info.maxDistance = 0;
            return info;
        }

        // 左右递归收集子节点信息
        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right);

        Info info = new Info();
        //当前子树的最大距离 = 左子树的最大距离、右子树的最大距离、左子树高度+1+右子树高度,三者的最大值
        info.maxDistance = Math.max(Math.max(leftInfo.maxDistance, rightInfo.maxDistance), leftInfo.height + 1 + rightInfo.height);
        //当前子树的高度 = 左子树的高度、右子树的高度,二者中的最大值+1
        info.height = Math.max(leftInfo.height, rightInfo.height) + 1;
        return info;
    }

    private static class Info {
   
     
        private int height; // 树高度
        private int maxDistance; // 当前树的节点最大距离
    }

    private static class Node {
   
     
        private int value;
        private Node left;
        private Node right;
    }

}

给定一个二叉树,返回其二叉搜索子树中最大子树的节点数

也就是整棵二叉树可能是不满足搜索二叉树结构的,但是它的子树有可能是搜索二叉树,返回它的满足搜索二叉树结构的子树中,最大的子树的节点数。

三种情况:

  • 左子树中最大搜索二叉树节点数
  • 右子树中最大搜索二叉树节点数
  • 左右子树都是二叉搜索树,左子树的最大值 < 当前节点值 < 右子树的最小值,左右子树的节点数+1

所以需要的信息:

  • 左子树最大搜索二叉树节点数
  • 右子树最大搜索二叉树节点数
  • 左子树最大值
  • 右子树最小值
  • 左子树是否搜索二叉树
  • 右子树是否搜索二叉树

 

/**
 * 给定一个二叉树,返回其二叉搜索子树中最大子树的结点数
 */
public class TreeRecursion03 {
   
     

    public static int findMaxSubAllBSTSize(Node head) {
   
     
        if (head == null) return 0;
        Info info = process(head);
        return info.maxSubAllBSTSize;
    }

    private static Info process(Node node) {
   
     
        if (node == null) return null;

        // 递归收集左右节点信息
        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right);

        boolean isAllBST; //是否是二叉搜索树
        int maxSubAllBSTSize; //最大二叉搜索子树的结点数
        int max; //当前子树最大值
        int min; //当前子树最小值

        //根据从左右子树收集回来的信息,计算当前节点的max,min
        max = node.value;
        min = node.value;
        if (leftInfo != null) {
   
     
            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);
        }

        //预设当前子树非二叉搜索数,最大二叉搜索子树节点数位左子树和右子树中maxSubAllBSTSize的最大值
        isAllBST = false;
        maxSubAllBSTSize = Math.max((leftInfo == null ? 0 : leftInfo.maxSubAllBSTSize), (rightInfo == null ? 0 : rightInfo.maxSubAllBSTSize));

        //判断当前子树是否是二叉搜索数,是的话,更新isAllBST,maxSubAllBSTSize
        if ((leftInfo == null || leftInfo.isAllBST) //左子树是二叉搜索树
                && ((rightInfo == null || rightInfo.isAllBST)) //右子树是二叉搜索树
                && (leftInfo == null || leftInfo.max < node.value) //左子树的最大值小于当前节点的值
                && (rightInfo == null || rightInfo.min > node.value) //右子树的最小值大于当前节点的值
                ) {
   
     
            isAllBST = true;
            maxSubAllBSTSize = (leftInfo == null ? 0 : leftInfo.maxSubAllBSTSize) + 1 + (rightInfo == null ? 0 : rightInfo.maxSubAllBSTSize);
        }

        // 整合当前子树信息,返回
        Info info = new Info();
        info.isAllBST = isAllBST;
        info.maxSubAllBSTSize = maxSubAllBSTSize;
        info.max = max;
        info.min = min;
        return info;
    }

    private static class Info {
   
     
        private boolean isAllBST; //是否是二叉搜索树
        private int maxSubAllBSTSize; //最大二叉搜索子树的结点数
        private int max; //当前子树最大值
        private int min; //当前子树最小值
    }

    private static class Node {
   
     
        private int value;
        private Node left;
        private Node right;
    }

}

开心派对问题

一个公司开派对,可以决定某个员工来或者不来。如果一个员工来,则直接下级不能来。每个员工都有自己的快乐值,0个或者若干个直接下级。求派对的最大快乐值(所有来参加派对的员工的快乐值之和)。

当前节点为头的子树的最大快乐值:

  • 头节点来,则头节点的自己快乐值 + 它的所有子节点不来时的最大快乐值
  • 头节点不来,在它的所有子节点的 Math.max(来的最大收益,不来的最大收益) 相加

所以需要信息:

  • 当前节点来时,以它为头的子树的最大收益
  • 当前节点不来时,以它为头的子树的最大收益

 

/**
 1. 开心派对问题:
 2. 一个公司开派对,可以决定某个员工来或者不来
 3. 如果一个员工来,则直接下级不能来
 4. 
 5. 每个员工都有自己的快乐值,0个或者若干个直接下级
 6. 
 7. 求派对的最大快乐值(所有来参加派对的员工的快乐值之和)
 */
public class TreeRecursion04 {
   
     
    
    public static int findMaxHappy(Employee boss) {
   
     
        Info info = process(boss);
        return Math.max(info.maxHappy1, info.maxHappy2);
    }

    private static Info process(Employee employee) {
   
     
        // base case:没有子节点,来时最大快乐值是自己的开了值,不来时的最大快乐值则是0
        if (employee.nexts.isEmpty()) {
   
     
            Info info = new Info();
            info.maxHappy1 = employee.happy;
            info.maxHappy2 = 0;
            return info;
        }

        int maxHappy1 = 0; //该员工来时,子树的最大快乐值
        int maxHappy2 = 0; //该员工不来,子树的最大快乐值

        for (Employee next : employee.nexts) {
   
     
            Info nextInfo = process(next); // 收集所有子节点信息
            maxHappy1 += nextInfo.maxHappy2; //当前员工来,直接下级不能来,当前员工的快乐值+直接下级不来时最大快乐值
            maxHappy2 += Math.max(nextInfo.maxHappy1, nextInfo.maxHappy2); //当前员工不来,则取直接下级来时和不来的最大快乐值中的最大值
        }

        // 整合当前节点信息返回
        Info info = new Info();
        info.maxHappy1 = maxHappy1;
        info.maxHappy2 = maxHappy2;
        return info;
    }

    private static class Info {
   
     
        private int maxHappy1; //该员工来时,子树的最大快乐值
        private int maxHappy2; //该员工不来,子树的最大快乐值
    }
    
    private static class Employee {
   
     
        private int happy;
        private List<Employee> nexts;
    }
    
}

给定一颗二叉树,判断其是否是满二叉树

解法:

1、 定义信息体,包含树高和数节点数两个信息;
2、 递归收集二叉树的信息,得到根节点信息;
3、 用根节点信息进行计算,((1<<info.height)+1)==info.size为true,则时满二叉树;

/**
 * 给定一颗二叉树,判断其是否是满二叉树
 */
public class TreeRecursion05 {
   
     

    public static boolean isFull(Node head) {
   
     
        Info info = process(head);
        return ((1 << info.height) + 1) == info.size;
    }

    private static Info process(Node node) {
   
     
        if (node == null) {
   
     
            Info info = new Info();
            info.size = 0;
            info.height = 0;
            return info;
        }
        
        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right);

        Info info = new Info();
        info.size = leftInfo.size + 1 + rightInfo.size;
        info.height = Math.max(leftInfo.height, rightInfo.height) + 1;
        return info;
    }

    private static class Info {
   
     
        private int height;
        private int size;
    }

    private static class Node {
   
     
        private int value;
        private Node left;
        private Node right;
    }

}

给定一个二叉树,返回其二叉搜索子树中最大子树的头结点

与“求最大二叉搜索子树中的节点数”的解法类似

/**
 * 给定一个二叉树,返回其二叉搜索子树中最大子树的头结点
 */
public class TreeRecursion06 {
   
     

    public static Node findMaxSubBSTHead(Node head) {
   
     
        Info info = process(head);
        return info == null ? null : info.maxSubBSTHead;
    }

    private static Info process(Node node) {
   
     
        if (node == null) return null;

        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right);

        //预设当前子树不是二叉搜索树,从左右子树返回的信息中,计算max、min、maxSubBSTSize、maxSubBSTHead
        Info info = new Info();
        info.max = node.value;
        info.min = node.value;
        info.maxSubBSTSize = 0;
        if (leftInfo != null) {
   
     
            info.max = Math.max(leftInfo.max, info.max);
            info.min = Math.min(leftInfo.min, info.min);
            info.maxSubBSTSize = leftInfo.maxSubBSTSize;
            info.maxSubBSTHead = leftInfo.maxSubBSTHead;
        }
        if (rightInfo != null) {
   
     
            info.max = Math.max(rightInfo.max, info.max);
            info.min = Math.min(rightInfo.min, info.min);
            if (rightInfo.maxSubBSTSize > info.maxSubBSTSize) {
   
     
                info.maxSubBSTHead = rightInfo.maxSubBSTHead;
                info.maxSubBSTSize = rightInfo.maxSubBSTSize;
            }
        }

        //判断当前子树是否是二叉搜索树,若是则maxSubBSTHead设置为当前结点,重新计算maxSubBSTSize
        if ((leftInfo == null || leftInfo.maxSubBSTHead == node.left)
                && (rightInfo == null || rightInfo.maxSubBSTHead == node.right)
                && (leftInfo == null || leftInfo.max < node.value)
                && (rightInfo == null || rightInfo.min > node.value)) {
   
     
            info.maxSubBSTHead = node;
            info.maxSubBSTSize = (leftInfo == null ? 0 : leftInfo.maxSubBSTSize) + 1 + (rightInfo == null ? 0 : rightInfo.maxSubBSTSize);
        }

        return info;
    }

    private static class Info {
   
     
        private Node maxSubBSTHead; //最大二叉搜索子树头结点
        private int maxSubBSTSize; //最大二叉搜索子树大小
        private int max; //子树最大值
        private int min; //子树最小值
    }

    private static class Node {
   
     
        private int value;
        private Node left;
        private Node right;
    }

}

给定一颗二叉树,判断其是否是完全二叉树

四种情况:

  • 整棵树是满二叉树
  • 左子树是完全二叉树,右子树是满二叉树,左子树比右子树高度高1
  • 左子树是满二叉树,右子树是满二叉树,左子树比右子树高度高1
  • 左子树是满二叉树,右子树是完全二叉树,左右子树高度相同

所以需要信息:

  • 以当前节点为头的树是否是满二叉树
  • 以当前节点为头的树是否是完全二叉树
  • 以当前节点为头的树的树高
/**
 * 给定一颗二叉树,判断其是否是完全二叉树
 *
 * 四种情况:
 * 1.整棵树是满二叉树
 * 2.左子树是完全二叉树,右子树是满二叉树,左子树比右子树高度高1
 * 3.左子树是满二叉树,右子树是满二叉树,左子树比右子树高度高1
 * 4.左子树是满二叉树,右子树是完全二叉树,左右子树高度相同
 */
public class TreeRecursion07 {
   
     

    public static boolean isCBT(Node head) {
   
     
        Info info = process(head);
        return info.isCBT;
    }

    private static Info process(Node node) {
   
     

        // base caes:空树,是满二叉树,是完全二叉树,树高0
        if (node == null) {
   
     
            Info info = new Info();
            info.isCBT = true;
            info.isFull = true;
            info.height = 0;
            return info;
        }

        // 从左右子树收集信息
        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right);

        // 根据从左右子树收集回来的信息,计算height和isFull
        Info info = new Info();
        info.height = Math.max(leftInfo.height, rightInfo.height) + 1;
        info.isFull = leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height;

        // 根据从左右子树收集回来的信息,计算isCBT
        if (info.isFull) {
   
     
            info.isCBT = true; //满足条件1
        } else {
   
     
            if (leftInfo.isCBT && rightInfo.isCBT) {
   
     

                if ((leftInfo.isCBT && rightInfo.isFull && leftInfo.height - rightInfo.height == 1) //满足条件2
                        || (leftInfo.isFull && rightInfo.isFull && leftInfo.height - rightInfo.height == 1) //满足条件3
                        || (leftInfo.isFull && rightInfo.isCBT && leftInfo.height == rightInfo.height)) {
   
      //满足条件4
                    info.isCBT = true;
                }

            }
        }

        return info;
    }

    private static class Info {
   
     
        private boolean isFull; //当前子树是否是满二叉树
        private boolean isCBT; //当前子树是否是完全二叉树
        private int height; //当前子树高度
    }

    private static class Node {
   
     
        private int value;
        private Node left;
        private Node right;
    }

}

二叉树中寻找两个结点的最低公共祖先

普通方法:

1、 遍历一遍二叉树,用一个map记录子节点和父节点的映射关系;
2、 先挑其中一个节点,沿着map往上找,找到的节点记录到set中;
3、 再拿另一个节点,沿着map往上找,找到在set中存在的节点,返回这个结点;

树形DP解法:

假设要求a节点和b节点的最低公共祖先,从左右子树收集信息,是否发现a节点,是否发现b节点,如果都发现了,记录当前节点是答案节点。

树形DP解法需要收集的信息:

  • 子树答案节点
  • 是否发现a节点
  • 是否发现b节点
/**
 * 二叉树中寻找两个结点的最低公共祖先
 */
public class TreeRecursion08 {
   
     

    public static Node findLowestAncestor(Node head, Node node1, Node node2) {
   
     
        Info info = process(head, node1, node2);
        return info == null ? null : info.result;
    }

    private static Info process(Node node, Node node1, Node node2) {
   
     
        if (node == null) return null;

        //分别往左右子树收集信息
        Info leftInfo = process(node, node1, node2);
        Info rightInfo = process(node, node1, node2);

        //根据左右子树的信息,计算findNode1和findNode2
        boolean findNode1 = node == node1 || leftInfo.findNode1 || rightInfo.findNode1;
        boolean findNode2 = node == node2 || leftInfo.findNode2 || rightInfo.findNode2;

        //如果左子树或右子树返回的信息中已经记录了最低公共祖先,则记录到当前节点的信息中,往上返回
        Node result = null;
        if (leftInfo.result != null) result = leftInfo.result;
        if (rightInfo.result != null) result = rightInfo.result;

        //到这里result依然为空,则根据findNode1和findNode2的值进行计算,如果都为true,代表当前这个结点就是最低公共祖先
        if (result == null) {
   
     
            if (findNode1 && findNode2) result = node;
        }

        Info info = new Info();
        info.result = result;
        info.findNode1 = findNode1;
        info.findNode2 = findNode2;
        return info;
    }

    private static class Info {
   
     
        private Node result; //node1和node2的最低公共祖先
        private boolean findNode1; //是否已经找到了node1
        private boolean findNode2; //是否已经找到了node2
    }

    private static class Node {
   
     
        private int value;
        private Node left;
        private Node right;
    }

}