12 二叉树递归（树形DP）

第12节.pptx

二叉树的递归套路

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

题目1：是否为完全二叉树

完全二叉树：二叉树每一层节点都是满的，如有有节点不满的层，那一定是最后一层，且有从左往右变满的趋势

// 判断二叉树是否是完全二叉树
// 完全二叉树：树的每一层都是满树，就算不满，也是最后一层不满，也是从左往右变满的趋势
public static boolean completeBT(TreeNode root) {
    if (root == null) {
        return true;
    }
    // 二叉树按层遍历
    LinkedList<TreeNode> queue = new LinkedList<>();
    boolean hasNoChild = false;
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        TreeNode leftChild = node.left;
        TreeNode rightChild = node.right;
        // 遇到hasNoChild的节点后，后面的节点必须是叶节点（没有2个孩子）
        if (hasNoChild && (leftChild != null || rightChild != null)) {
            return false;
        }
        // 没有左孩子，有有孩子，直接返回false
        if (rightChild != null && leftChild == null) {
            return false;
        }
        if (leftChild != null) {
            queue.offer(leftChild);
        }
        if (rightChild != null) {
            queue.offer(rightChild);
        }
        // 第一次遇到没有孩子的节点后,将hasNoChild 设为true
        if (leftChild == null || rightChild == null) {
            hasNoChild = true;
        }
    }
    return true;
}

public static boolean completeBT2(TreeNode root) {
    if (root == null) {
        return true;
    }
    return process(root).completeBT;
}
private static class Info {
    boolean fullTree;
    boolean completeBT;
    int heigth;
    public Info(boolean fullTree, boolean completeBT, int heigth) {
        this.fullTree = fullTree;
        this.completeBT = completeBT;
        this.heigth = heigth;
    }
}
private static Info process(TreeNode node) {
    if (node == null) {
        return new Info(true, true, 0);
    }
    Info leftInfo = process(node.left);
    Info rightInfo = process(node.right);
    //1 以node为根节点的二叉树是否为满二叉树：左子树为满二叉树，右子树为满二叉树，同时左子树与右子树一样高
    boolean fullTree = leftInfo.fullTree && rightInfo.fullTree && leftInfo.heigth == rightInfo.heigth;
    //2 以node为根节点的二叉树的高度，左子树和右子树最大高度+1
    int height = Math.max(leftInfo.heigth, rightInfo.heigth) + 1;
    //3 以node为根节点的二叉树是否为完全二叉树，先设为false
    boolean completeBT = false;
    //3.1 如果以node为根节点的二叉树是满二叉树，那么一定是完全二叉树
    if (fullTree) {
        completeBT = true;
    } else {
        boolean differ = (leftInfo.heigth - rightInfo.heigth == 1);
        //3.2  如果以node为根节点的二叉树不是满二叉树,但是做子树和右子树是满二叉树
        if (leftInfo.fullTree && rightInfo.fullTree) {
            //3.2.1 左子树、右子树都是满树，那么只有左子树比右子树多1层，以node为根节点的二叉树才是完全二叉树
            if (differ) {
                completeBT = true;
            }
        } else if (!leftInfo.fullTree && rightInfo.fullTree) {
            //3.2.2 左子树不是满树，右子树是满树，那么必须左子树是完全二叉树，左子树比右子树多1层
            if (leftInfo.completeBT && differ) {
                completeBT = true;
            }
        } else if (leftInfo.fullTree) {
            //3.2.3 左子树是满树，右子树不是满树，那么必须右子树必须是完全二叉树，左子树和右子树一样高
            if (rightInfo.completeBT && (leftInfo.heigth == rightInfo.heigth)) {
                completeBT = true;
            }
        }
    }
    return new Info(fullTree, completeBT, height);
}

题目2：是否为搜索二叉树

搜索二叉树：搜索二叉树每一个节点值都不相同，且根节点的值大于左子树的最大值，小于右子树最小值

public static boolean isSearchBT2(TreeNode root) {
    if (root == null) {
        return true;
    }
    ArrayList<TreeNode> arr = new ArrayList<>();
    in(root, arr);
    for (int i = 0; i < arr.size() - 1; i++) {
        if (arr.get(i).value >= arr.get(i + 1).value) {
            return false;
        }
    }
    return true;
}
private static void in(TreeNode node, ArrayList<TreeNode> arr) {
    if (node == null) {
        return;
    }
    in(node.left, arr);
    arr.add(node);
    in(node.right, arr);
}

//判断二叉树是否是搜索二叉树
// 搜索二叉树，左子树最大值小于头结点，右子树最小值大于头结点的值
public static boolean isSearchBT(TreeNode root) {
    if (root == null) {
        return true;
    }
    return process(root).searchTree;
}
private static class Info {
    boolean searchTree;
    int maxValue;
    int minValue;
    public Info(boolean searchTree, int maxValue, int minValue) {
        this.searchTree = searchTree;
        this.maxValue = maxValue;
        this.minValue = minValue;
    }
}
private static Info process(TreeNode node) {
    if (node == null) {
        return null;
    }
    Info leftInfo = process(node.left);
    Info rightInfo = process(node.right);
    int maxValue = node.value;
    int minValue = node.value;
    if (leftInfo != null) {
        maxValue = Math.max(maxValue, leftInfo.maxValue);
        minValue = Math.min(minValue, leftInfo.minValue);
    }
    if (rightInfo != null) {
        maxValue = Math.max(maxValue, rightInfo.maxValue);
        minValue = Math.min(minValue, rightInfo.minValue);
    }
    boolean searchTree = false;
    if (leftInfo != null && rightInfo != null) {
        searchTree = leftInfo.searchTree && rightInfo.searchTree && (leftInfo.maxValue < node.value) && (rightInfo.minValue > node.value);
    } else if (rightInfo != null) {
        searchTree = rightInfo.searchTree && (rightInfo.minValue > node.value);
    } else if (leftInfo != null) {
        searchTree = leftInfo.searchTree && (leftInfo.maxValue < node.value);
    } else {
        searchTree = true;
    }
    return new Info(searchTree, maxValue, minValue);
}

题目3：是否为平衡二叉树

平衡二叉树：任一节点对应的两棵子树的最大高度差为1，因此它也被称为平衡二叉树

//是否为平衡二叉树
// 平衡二叉树，任一节点对应的两棵子树的最大高度差为1，因此它也被称为平衡二叉树
public static boolean isBalancedTree(TreeNode root) {
    if (root == null) {
        return true;
    }
    return process(root).balancedTree;
}
private static class Info {
    boolean balancedTree;
    int height;
    public Info(boolean balancedTree, int height) {
        this.balancedTree = balancedTree;
        this.height = height;
    }
}
private static Info process(TreeNode node) {
    if (node == null) {
        return new Info(true, 0);
    }
    Info leftInfo = process(node.left);
    Info rightInfo = process(node.right);
    int height = Math.max(leftInfo.height, rightInfo.height) + 1;
    boolean balancedTree = leftInfo.balancedTree && rightInfo.balancedTree && (Math.abs(leftInfo.height - rightInfo.height) < 2);
    return new Info(balancedTree, height);
}

public static boolean isBalancedTree2(TreeNode root) {
    if (root == null) {
        return true;
    }
    boolean[] ans = {true};
    process2(root, ans);
    return ans[0];
}

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

题目4：是否为满二叉树

满二叉树：每一层节点都是满

// 第1种方法
// 收集子树是否是满二叉树
// 收集子树的高度
// 左树满 && 右树满 && 左右树高度一样 -> 整棵树是满的

public static boolean isFullTree(TreeNode root) {
    if (root == null) {
        return true;
    }
    return precess(root).full;
}

private static class Info {
    int height;
    boolean full;

    public Info(int height, boolean full) {
        this.height = height;
        this.full = full;
    }
}

private static Info precess(TreeNode node) {
    if (node == null) {
        return new Info(0, true);
    }
    Info leftInfo = precess(node.left);
    Info rightInfo = precess(node.right);

    int height = Math.max(leftInfo.height, rightInfo.height) + 1;
    boolean full = leftInfo.full && rightInfo.full && leftInfo.height == rightInfo.height;
    return new Info(height, full);
}

public static boolean isFullTree2(TreeNode root) {
    if (root == null) {
        return true;
    }
    Info2 info2 = process2(root);
    return info2.nodes == (1 << info2.height) - 1;

}

// 第2种方法
// 收集整棵树的高度h，和节点数n
// 只有满二叉树满足 : 2 ^ h - 1 == n

private static class Info2 {
    int height;
    int nodes;

    public Info2(int height, int nodes) {
        this.height = height;
        this.nodes = nodes;
    }
}

private static Info2 process2(TreeNode node) {
    if (node == null) {
        return new Info2(0, 0);
    }
    Info2 leftInfo = process2(node.left);
    Info2 rightInfo = process2(node.right);
    int nodes = leftInfo.nodes + rightInfo.nodes + 1;
    int height = Math.max(leftInfo.height, rightInfo.height) + 1;
    return new Info2(height, nodes);
}

题目5：返回二叉树最大的二叉搜索子树的大小

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

public static int maxSBTSize(TreeNode root) {
    if (root == null) {
        return 0;
    }
    return precess(root).maxSBTSize;
}

private static class Info {
    int maxSBTSize;
    int size;
    int max;
    int min;

    public Info(int maxSBTSize, int size, int max, int min) {
        this.maxSBTSize = maxSBTSize;
        this.size = size;
        this.max = max;
        this.min = min;
    }
}

private static Info precess(TreeNode node) {
    if (node == null) {
        return null;
    }

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

    int size = 1;
    int max = node.value;
    int min = node.value;

    if (leftInfo != null) {
        size += leftInfo.size;
        max = Math.max(max, leftInfo.max);
        min = Math.min(min, leftInfo.min);
    }
    if (rightInfo != null) {
        size += rightInfo.size;
        max = Math.max(max, rightInfo.max);
        min = Math.min(min, rightInfo.min);
    }

    int p1 = leftInfo != null ? leftInfo.maxSBTSize : 0;
    int p2 = rightInfo != null ? rightInfo.maxSBTSize : 0;
    int p3 = 0;
    boolean leftIsSearchTree = leftInfo == null || leftInfo.maxSBTSize == leftInfo.size;
    boolean rightSearchTree = rightInfo == null || rightInfo.maxSBTSize == rightInfo.size;

    if (leftIsSearchTree && rightSearchTree) {
        boolean leftMaxLessNode = leftInfo == null || leftInfo.max < node.value;
        boolean rightMinMoreNode = rightInfo == null || rightInfo.min > node.value;
        if (leftMaxLessNode && rightMinMoreNode) {
            int leftSize = leftInfo == null ? 0 : leftInfo.size;
            int rightSize = rightInfo == null ? 0 : rightInfo.size;
            p3 = leftSize + rightSize + 1;
        }
    }
    int maxSBTSize = Math.max(p1, Math.max(p2, p3));
    return new Info(maxSBTSize, size, max, min);
}

public static int maxSBTSize2(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int bstSize = getBSTSize(root);
    if (bstSize != 0) {
        return bstSize;
    }
    return Math.max(maxSBTSize2(root.left), maxSBTSize2(root.right));
}

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

private static void in(TreeNode node, ArrayList<TreeNode> arr) {
    if (node == null) {
        return;
    }
    in(node.left, arr);
    arr.add(node);
    in(node.right, arr);
}

题目6：返回整棵二叉树的最大距离

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

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

public static int maxDistance(TreeNode root) {
    if (root == null) {
        return 0;
    }
    return process(root).maxDistance;
}


private static class Info {
    int height;
    int maxDistance;

    public Info(int height, int maxDistance) {
        this.height = height;
        this.maxDistance = maxDistance;
    }
}

private static Info process(TreeNode node) {
    if (node == null) {
        return new Info(0, 0);
    }
    Info leftInfo = process(node.left);
    Info rightInfo = process(node.right);

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

public static int maxDistance2(TreeNode head) {
    if (head == null) {
        return 0;
    }
    ArrayList<TreeNode> arr = getPrelist(head);
    HashMap<TreeNode, TreeNode> 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<TreeNode> getPrelist(TreeNode head) {
    ArrayList<TreeNode> arr = new ArrayList<>();
    fillPrelist(head, arr);
    return arr;
}

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

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

public static void fillParentMap(TreeNode head, HashMap<TreeNode, TreeNode> 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<TreeNode, TreeNode> parentMap, TreeNode o1, TreeNode o2) {
    HashSet<TreeNode> o1Set = new HashSet<>();
    TreeNode 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);
    }
    TreeNode 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;
}

题目7：返回这颗二叉树中最大的二叉搜索子树的头节点

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

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

public static TreeNode maxSubSearchTreeHead(TreeNode root) {
    if (root == null) {
        return null;
    }
    return process(root).head;
}

private static class Info {
    int subSearchTreeSize;
    int max;
    int min;
    TreeNode head;

    public Info(int subSearchTreeSize, int max, int min, TreeNode head) {
        this.subSearchTreeSize = subSearchTreeSize;
        this.max = max;
        this.min = min;
        this.head = head;
    }
}

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

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

    int subSearchTreeSize = 0;
    int max = node.value;
    int min = node.value;
    TreeNode head = null;

    if (leftInfo != null) {
        max = Math.max(leftInfo.max, max);
        min = Math.min(leftInfo.min, min);
        subSearchTreeSize = leftInfo.subSearchTreeSize;
        head = leftInfo.head;
    }
    if (rightInfo != null) {
        max = Math.max(rightInfo.max, max);
        min = Math.min(rightInfo.min, min);
        if (rightInfo.subSearchTreeSize > subSearchTreeSize) {
            subSearchTreeSize = rightInfo.subSearchTreeSize;
            head = rightInfo.head;
        }
    }
    // 左子树为空或者左子树为搜索树，且左子树最大值小于头结点值
    boolean leftBool = leftInfo == null || ((leftInfo.head == node.left) && (leftInfo.max < node.value));
    // 右子树为空或者右子树为搜索树，且右子树最小值大于头结点值
    boolean rightBool = rightInfo == null || ((rightInfo.head == node.right) && (rightInfo.min > node.value));
    // 左子树、右子树满足条件
    if (leftBool && rightBool) {
        head = node;
        subSearchTreeSize = (leftInfo == null ? 0 : leftInfo.subSearchTreeSize) + (rightInfo == null ? 0 : rightInfo.subSearchTreeSize) + 1;
    }
    return new Info(subSearchTreeSize, max, min, head);
}

public static TreeNode maxSubSearchTreeHead2(TreeNode head) {
    if (head == null) {
        return null;
    }
    int bstSize = getBSTSize(head);
    // 不为0，则head为头结点的二叉树为搜索二叉树
    if (bstSize != 0) {
        return head;
    }
    // 左子树返回的头结点
    TreeNode left = maxSubSearchTreeHead2(head.left);
    // 右子树返回的头结点
    TreeNode right = maxSubSearchTreeHead2(head.right);
    // 返回左、右子树头结点子树size大的子树头结点
    return getBSTSize(left) >= getBSTSize(right) ? left : right;


}
// 获取以node为头结点的搜索树的大小 node为空或不是搜索树返回0
private static int getBSTSize(TreeNode node) {
    if (node == null) {
        return 0;
    }
    ArrayList<TreeNode> arr = new ArrayList<>();
    in(node, arr);
    for (int i = 0; i < arr.size()-1; i++) {
        if (arr.get(i).value >= arr.get(i + 1).value) {
            return 0;
        }
    }
    return arr.size();
}
// 中序遍历放入ArrayList<TreeNode>集合中
private static void in(TreeNode node, ArrayList<TreeNode> arr) {
    if (node == null) {
        return;
    }
    in(node.left, arr);
    arr.add(node);
    in(node.right, arr);
}

题目8：返回两个节点最低公共祖先

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

//给定一棵二叉树的头节点head，和另外两个节点a和b。
//返回a和b的最低公共祖先
public static TreeNode lowestAncestor(TreeNode head, TreeNode a, TreeNode b) {
    if (head == null) {
        return null;
    }

    return process(head, a, b).lowestAncestor;
}

private static class Info {
    boolean findA;
    boolean findB;
    TreeNode lowestAncestor;

    public Info(boolean findA, boolean findB, TreeNode lowestAncestor) {
        this.findA = findA;
        this.findB = findB;
        this.lowestAncestor = lowestAncestor;
    }
}

private static Info process(TreeNode node, TreeNode a, TreeNode b) {
    if (node == null) {
        return new Info(false, false, null);
    }

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

    boolean findA = leftInfo.findA || rightInfo.findA || node == a;
    boolean findB = leftInfo.findB || rightInfo.findB || node == b;
    TreeNode lowestAncestor = null;

    if (leftInfo.lowestAncestor != null) {
        lowestAncestor = leftInfo.lowestAncestor;
    } else if (rightInfo.lowestAncestor != null) {
        lowestAncestor = rightInfo.lowestAncestor;
    } else if (findA && findB) {
        lowestAncestor = node;
    }
    return new Info(findA, findB, lowestAncestor);
}

public static TreeNode lowestAncestor2(TreeNode head, TreeNode a, TreeNode b) {
    if (head == null) {
        return null;
    }
    Map<TreeNode, TreeNode> parentMap = new HashMap<>();
    parentMap.put(head, null);
    fillParentMap(head, parentMap);
    Set<TreeNode> set1 = new HashSet<>();
    TreeNode cur = a;
    set1.add(cur);
    while (parentMap.get(cur) != null) {
        cur = parentMap.get(cur);
        set1.add(cur);
    }
    cur = b;
    while (!set1.contains(cur)) {
        cur = parentMap.get(cur);
    }
    return cur;
}

public static void fillParentMap(TreeNode head, Map<TreeNode, TreeNode> 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);
    }
}

题目9：派对的最大快乐值

公司的每个员工都符合 Employee 类的描述。整个公司的人员结构可以看作是一棵标准的、 没有环的多叉树。树的头节点是公司唯一的老板。除老板之外的每个员工都有唯一的直接上级。 叶节点是没有任何下属的基层员工(subordinates列表为空)，除基层员工外，每个员工都有一个或多个直接下级。
这个公司现在要办party，你可以决定哪些员工来，哪些员工不来，规则：
1.如果某个员工来了，那么这个员工的所有直接下级都不能来
2.派对的整体快乐值是所有到场员工快乐值的累加
3.你的目标是让派对的整体快乐值尽量大
给定一棵多叉树的头节点boss，请返回派对的最大快乐值。

private static class Employee {
    int happy;
    List<Employee> subordinates;

    public Employee(int happy) {
        this.happy = happy;
        subordinates = new ArrayList<>();
    }
}

public static int maxHappy(Employee boss) {
    if (boss == null) {
        return 0;
    }
    Info bossInfo = process(boss);
    return Math.max(bossInfo.noAttendMaxHappy, bossInfo.attendMaxHappy);
}

private static class Info {
    int attendMaxHappy;
    int noAttendMaxHappy;

    public Info(int attendMaxHappy, int noAttendMaxHappy) {
        this.attendMaxHappy = attendMaxHappy;
        this.noAttendMaxHappy = noAttendMaxHappy;
    }
}

private static Info process(Employee employee) {
    if (employee == null) {
        return new Info(0, 0);
    }
    int attendMaxHappy = employee.happy;
    int noAttendMaxHappy = 0;

    for (Employee subordinate : employee.subordinates) {
        Info info = process(subordinate);
        attendMaxHappy += info.noAttendMaxHappy;
        noAttendMaxHappy += Math.max(info.attendMaxHappy, info.noAttendMaxHappy);
    }
    return new Info(attendMaxHappy, noAttendMaxHappy);
}

public static int maxHappy2(Employee boss) {
    if (boss == null) {
        return 0;
    }
    return process2(boss, false);
}
// 当前员工和上级是否参加
private static int process2(Employee cur, boolean leaderAttend) {
    // 上级参加，那么当前员工不参加
    if (leaderAttend) {
        int ans = 0;
        for (Employee c : cur.subordinates) {
            ans += process2(c, false);
        }
        return ans;
    } else {
        // 上级不参加，当前员工可参加，也可不参加
        int p1 = cur.happy;
        int p2 = 0;
        for (Employee c : cur.subordinates) {
            p1 += process2(c, true);
            p2 += process2(c, false);
        }
        return Math.max(p1, p2);
    }
}