1993. 树上的操作 (opens new window)

1.哈希

难点在于update实现，需要遍历当前节点的祖先节点和子树。其中祖先节点直接根据parent数组遍历；子树则需要建立哈希表保存节点的孩子节点，递归map的子节点。

class LockingTree {
    private static class Node{
        int userId;
        int parentId;
        boolean lock;
    }
    Node[] tree;
    Map<Integer,List<Integer>> map;
    public LockingTree(int[] parent) {
        map=new HashMap<>();
        tree=new Node[parent.length];
        for(int i=0;i<parent.length;i++){
            tree[i]=new Node();
            tree[i].parentId=parent[i];
            if(map.containsKey(parent[i])){
                map.get(parent[i]).add(i);
            }
            else{
                List<Integer> list = new ArrayList<>();
                list.add(i);
                map.put(parent[i], list);
            }
        }
    }
    public boolean lock(int num, int user) {
        if(!tree[num].lock){
            tree[num].lock=true;
            tree[num].userId=user;
            return true;
        }
        else{
            return false;
        }
    }
    public boolean unlock(int num, int user) {
        if(tree[num].lock&&tree[num].userId==user){
            tree[num].lock=false;
            return true;
        }
        else return false;
    }
    public boolean upgrade(int num, int user) {
        int father=tree[num].parentId;
        boolean checkFather=false;
        while(father!=-1){
            if(tree[father].lock){
                checkFather=true;
                break;
            }
            father=tree[father].parentId;
        }
        boolean checkSon=map.containsKey(num)?check(num):false;
        if(checkFather||tree[num].lock||!checkSon) return false;

        release(num);
        tree[num].userId=user;
        tree[num].lock=true;
        return true;

    }
    public boolean check(int num){
        for(Integer i:map.get(num)){
            if(tree[i].lock)return true;
            if(map.containsKey(i)&&check(i)) return true;
        }
        return false;
    }
    public void release(int num){
        for(Integer i:map.get(num)){
            tree[i].lock=false;
            if(map.containsKey(i)) release(i);
        }
    }
}