算法-二叉树相关题目

二叉树题目思路

思路

1. 先求出当前二叉树的左树和右树的相关信息
2. 对左树和右树的信息做处理，返回当前树的信息

题目

找到最大BST子树

题目：给定一个二叉树，找到其中最大的二叉搜索树（BST）子树，其中最大指的是子树节点数最多的。注意:子树必须包含其所有后代。

思路：

1. 首先判断当前左树是否是BST，右树是否是BST，如果都是，则记录当前子节点个数为max，同时记录当前树总结点个数
2. 因此，info类可以有5个信息，分别是isBST,maxNode,allNode,max,min

public class Info{
    public boolean isBST;
    public int maxNode;
    public int allNode;
    public int max;
    public int min
    
    public Info(int maxN,int allN,int max,int min,boolean i){
        this.maxNode = max;
        this.allNode= all;
        this.max = max;
        this.min = min;
        this.isBST = i;
    }
}

public Info process1(Node head){
    if(head == null){
        return new Info(0,0,Integer.MIN_VALUE,Integer.MAX_VALUE,true);
    }
    Info leftInfo = process1(head.left);
    Info rightInfo = process1(head.right);
    int maxNode = Math.max(leftInfo.maxNode,rightInfo.maxNode);
    int allNode = leftInfo.allNode+rightInfo.allNode+1;
    int max = Math.max(Math.max(leftInfo.max,rightInfo.max),head.value);
    int min = Math.min(Math.min(leftInfo.min,rightInfo.min),head.value);
    boolean isBST = false;
    if(leftInfo.isBST && rightInfo.isBST){
        if(leftInfo.max < head.value && rightInfo.min > head.val){
            isBST = true;
            maxNode = allNode;
        }
    }
    return new Info(maxNode,allNode,max,min,isBST);
}

解法二：

思路：

1. 对每棵树进行遍历，判断每棵树是否都是BST，是，返回当前树的长度，不是，则返回0

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

public int getBSTSize(TreeNode root){
    List<Integer> list = new ArrayList<>();
    inOrder(root,list);
    for(int i= 0 ;i < list.size() - 1;i++){
        if(list.get(i) >= list.get(i+1)){
            return 0;
        }
    }
    return list.size();
}
public void inOrder(TreeNode root,List<Integer> list){
    if(root == null){
        return;
    }
    inOrder(root.left,list);
    list.add(root.value);
    inOrder(root.right,list);
}

二叉树的直径

题目：给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

public class TreeNode{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int v){
        this.val = ;
    }
}

解法一：

思路：

1. 当前结点左树的高度，右树的高度，左树的maxDistance，右树的maxDistance
2. 左树的高度+右树的高度 +1> maxDistance,则说明当前树的maxDistance是左右两树高+1
3. 因此，需要Info类(height,maxDistance)

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

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

public Info process(TreeNode root){
    if(root == null){
        return new Info(0,0);
    }
    Info leftInfo = process(root.left);
    Info rightInfo = process(root.right);
    int h = Math.max(leftInfo.height,rightInfo.height) + 1;
    int dis1 = Math.max(leftInfo.maxDistance,rightInfo.maxDistance);
    int dis2 = leftInfo.height + rightInfo.height + 1;
    dis = dis1 > dis2? dis1:dis2;
    return new Info(h,dis);
} 

解法二：

思路：

1. 当前两个节点的最大距离可以用hashMap和set求出
2. hashMap表示子父节点之间的关系
3. 节点p1，节点p2之间的最大距离必然是他们最近的公共祖先，只要知道这个公共祖先p3，就能得到最远距离
4. p1通过map向上寻找，把沿途的祖先节点放入set中，p2网上找，只要遇到set里拥有的，必然是第一个祖先节点
5. 然后获得第一个祖先节点gaf，两个节点网上找到gaf的路径就是最长路径
6. 暴力求解当前所有节点的最长路径

public static int right(TreeNode root) {
    if(root == null){
        return 0;
    }
    ArrayList<TreeNode> list = getPreList(head);
    HashMap<TreeNode,TreeNode> parnetMap = 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,List<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 staic int distance(Map<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(parentMap.get(cur) != null){
        cur = parentMap.get(cur);
    }
    TreeNode lowestAn = cur;
    cur = o1;
    int d1= 1;
    while(cur != lowestAn){
        cur = parentMap.get(cur);
        d1++;
    }
    cur = o2;
    int d2 = 1;
    while(cur != lowestAn){
        cur = parentMap.get(cur);
        d2++;
    }
    return d1+d2-1;
}

返回最大BST子树的头结点

题目：给定一个二叉树，找到其中最大的二叉搜索树（BST）子树，并返回头节点，其中最大指的是子树节点数最多的。注意:子树必须包含其所有后代。

public static class Node{
    public int value;
    public Node left;
    public Node right;
    public Node(int data){this.value = data;}
}

思路：

1. 左数是BST，有树是BST，且左树的max小于head.val,右树的min大于head.val，则当前树是BST
2. 当前树不是BST，则比较左树的node和右树的node谁多，谁多用谁的
3. 因此，可以设计一个info类,包含isBST，subBSTNode，subBSTNodes,allNodes,max,min

public static class Info{
    public boolean isBST;
    public int allNodes;
    public int subBSTNodes;
    public int max;
    public int min;
    public Node maxSubBSTNode;
    
    public Info(boolean isBST,int allNodes,int subBSTNodes,int max,int min,Node maxSubBSTNode){
        this.isBST = isBST;
        this.allNodes = allNodes;
        this.subBSTNodes = subBSTNodes;
        this.max = max;
        this.min = min;
        this.maxSubBSTNode = maxSubBSTNode;
    }
}

思路：

1. 判断左树是BST，右树是BST，当前树是BST，则subBSTNode更新为allNodes,isBST更新为true

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

public static Info process(Node head){
    if(head == null){
        return new Info{true,0,0,Integer.MIN_VALUE,Integer.MAX_VALUE,null};
    }
    Info leftInfo = process(head.left);
    Info rightInfo = process(head.right);
    int max = Math.max(Math.max(leftInfo.max, rightInfo.max), head.value);
    int min = Math.min(Math.min(leftInfo.min, rightInfo.min), head.value);
    boolean isBST = false;
    int allNodes = leftInfo.allNodes + rightInfo.allNodes + 1;
    int subBSTNodes = 0;
    Node maxSubBSTNode = null;
    if(leftInfo.isBST && rightInfo.isBST && leftInfo.max < head.value && rightInfo.min > head.value){
        subBSTNode = allNode;
        maxSubBSTNode = head;
        isBST = true;
    } else {
        subBSTNodes = leftInfo.subBSTNodes >= rightInfo.subBSTNodes ? leftInfo.subBSTNodes : rightInfo.subBSTNodes;
        maxSubBSTNode = leftInfo.subBSTNodes >= rightInfo.subBSTNodes ?
                    leftInfo.maxSubBSTNode : rightInfo.maxSubBSTNode;
            isBST = false;
    }
    return new Info(isBST,allNodes,subBSTNodes,max,min,maxSubBSTNode);
}

解法二：

思路：

1. 对当前每个节点循环遍历，判断每个节点本身是否是BST，如果当前节点是BST子树，则直接返回，无需比较他右侧和左侧的子树

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

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

public static void inOrder(Node head,List<Node> list){
    if(head == null){
        return;
    }
    inOrder(head.left,list);
    list.add(head);
    inOrder(head.right,list);
}

二叉树的公共祖先

题目：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

public static class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x){this.val = x;}
}

解法一：

思路：

1. 判断当前树是否有节点p，节点q，如果第一次同时拥有，则记录当前公共祖先，并返回
2. 因此可以弄一个Info类：haveP，haveQ，ans；

public static class Info {
    public boolean hasP;
    public boolean hasQ;
    public TreeNode ans;
    
    public Info(boolean hasP,boolean hasQ,TreeNode ans){
        this.hasP = hasP;
        this.hasQ = hasQ;
        this.ans = ans;
    }
}

public static TreeNode lowestCommonAncestor1(TreeNode root,TreeNode p,TreeNode q){
    if(root == null){
        return null;
    }
}

public static Info process(TreeNode root,TreeNode p,TreeNode q){
    if(root == null){
        return new Info(false,false,null);
    }
    Info left = process(root.left,p,q);
    Info right = process(root.right,p,q);
    boolean hasP = root == p || leftInfo.hasP || rightInfo.hasP;
    boolean hasQ = root == q || leftInfo.hasQ || rightInfo.hasQ;
    TreeNode ans = null;
    if(left.ans != null){
        ans = left.ans;
    } else if(right != null){
        ans = right.ans;
    } else {
        if(hasP && hasQ){
            ans = root;
        }
    }
    return new Info(hasP,hasQ,ans);
}

思路二：

1. 得到子父关系hashMap，然后通过p找到p祖先的set，然后再set里找q对应的第一个祖先，将他返回，就是最近公共祖先

public static TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
    if(root == null){
        return null;
    }
    Map<TreeNode,TreeNode> map = new HashMap<>();
    map.put(root,null);
    fillMap(root,map);
    
}

public static void fillMap(TreeNode root,Map map){
    if(root.left!=null){
        map.put(root.left,root);
        fillMap(root.left,map);
    }
    if(root.right!=null){
        map.put(root.right,root);
        fillMap(root.right,map);
    }
}

public static TreeNode findAns( TreeNode p, TreeNode q,Map map ){
    Set pSet = new HashSet();
    TreeNode c1 = p;
    TreeNode c2 = q;
    while(c1 != null){
        pSet.add(c1);
        map.get(c1);
    }
    while(c2 != null){
        if(pSet.contains(c2)){
            return c2;
        }
        c2 = map.get(c2);
    }
    return null;
}

比较器

思路：

1. 生成的随机二叉树用前序list记录下node，然后随机返回其中两个

public static TreeNode generateRandomBST(int maxLevel,int maxValue){
    return generate(1,maxLevel,maxValue);
}

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

public static TreeNode pickRandomOne(TreeNode root){
    if(root == null){
        return null;
    }
    ArrayList list = new ArrayList;
    fillList(root,list);
    int size = list.size();
    int random = (int)(Math.random() * size);
    return list.get(random);
}

public static void fillList(TreeNode root,ArrayList<TreeNode> list){
    if(root == null){
        return;
    }
    list.add(root);
    fillList(root.left,list);
    fillList(root.right,list);
}

排队的最大快乐值

题目：

员工信息的定义如下：

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

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

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

	1. 如果某个员工来了，那么这个员工的所有直接下级都不能来；
	2. 排队的整体快乐值是所有到场员工快乐值的累加；
	3. 你的目标是让排队的整体快乐值尽量大。
	4. 给定一棵多叉树的根节点 boss，请返回排队的最大快乐值。

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

解法一：

思路：

1. 该公司员工职级是多叉树
2. 该员工的总快乐值，有两种情况
   1. 当前员工来了，则当前这个员工的快乐值是他本身的happy+下属不来的maxHappy
   2. 当前员工不来，则当前这个员工的快乐值存在下属不来的maxHappy，和下属来的maxHappy
3. 因此，能对当前树需要的信息做一个总结：
   1. 当前树的头节点不来,各子树不来的maxVal或者个子树来的maxVal，从里面挑一个最大的，返回。
   2. 当前树的头节点来，则是val+各子树不来的maxVal。
4. 因此，可以设计一个Info类，包含no，yes，来和不来的最大值

public static class Info{
    public int no; //当前员工不来的最大值
    public int yes; //当前员工来的最大值
    
    public Info(int no,int yes){
        this.no = no;
        this.yes = yes;
    }
}

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

public static Info process2(Employee boss){
    if(boss == null){
        return new Info(0,0);
    }
    int no = 0;
    int yes = boss.val;
    for(Employee e : boss.nexts){
        Info eInfo = process(e);
        no += Math.max(eInfo.no,eInfo.yes);
        yes += eInfo.no;
    }
    return new Info(no,yes);
}

解法二：

思路：

1. 当前这个员工他的上司不来，则有当前员工不来的最大值和来的最大值，作比较
2. 当前这个员工的上司来，则当前员工不来的最大值

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

public static int process1(Employee boss,boolean up){
    if(boss == null){
        return 0;
    }
    
    if(up){
        int ans = 0;
        for(Employee e : boss.nexts){
        	ans += process1(e,false);
    	}
        return ans;
	} else {
        int no = 0;
    	int yes = boss.happy;
        for(Employee e : boss.nexts){
        	no += process1(e,false);
        	yes += process1(e,true);
    	}
        return Math.max(yes,no);
    }
}