算法刷题记录-树(LeetCode)

783. Minimum Distance Between BST Nodes

思路(DFS 中序遍历)

考虑中序遍历的性质即可

代码

class Solution {
public:
    int min_diff=numeric_limits<int>::max();
    int prev=numeric_limits<int>::min()+100000;
    int minDiffInBST(TreeNode* root) {
        inorderTraversal(root);
        return min_diff;
    }
    void inorderTraversal(TreeNode* root){
        if (root== nullptr){
            return ;
        }
        inorderTraversal(root->left);
        min_diff=min(min_diff,root->val-prev);
        prev=root->val;
        inorderTraversal(root->right);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

814. Binary Tree Pruning

思路(DFS)

对于一个节点是否删除，有如下几种情况:

863. All Nodes Distance K in Binary Tree

思路（DFS）

首先，需要通过dfs算法找到从原点到目标点的路径。$path=[2,3,5,7]$,$k=2$。其中7为目标点然后考虑对路径的每一节点，进行下列计算:
对于从原点到目标节点的路径。由目标点至上逐级考虑：

1. 对于目标点7，需要考虑所有距离目标节点距离为k的子节点(DFS)
2. 对于目标上一个节点5，从7至5的距离为1,因此考虑与5距离为1的子节点，同时将7设为已访问，防止重复遍历。
3. 。。。以此类推

代码

class Solution {
public:
    vector<int> ans;
    vector<TreeNode*> _path;
    vector<TreeNode*> path;
    unordered_set<int> visited;
    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
        _path.push_back(root);
        findPath(root,target->val);
        findNodes(path.back(),k);
        path.pop_back();
        k--;
        visited.insert(target->val);
        int size=path.size()-1;
        for (int i = size; i >=0 ; i--) {
            findNodes(path[i],k);
            visited.insert(path[i]->val);
            k--;
        }
        return ans;
    }
    void findPath(TreeNode* root,int target){
        if (root->val==target){
            for (auto curr:_path) {
                path.push_back(curr);
            }
            return;
        }
        if (root->left){
            _path.push_back(root->left);
            findPath(root->left,target);
            _path.pop_back();
        }
        if (root->right){
            _path.push_back(root->right);
            findPath(root->right,target);
            _path.pop_back();
        }
    }
    void findNodes(TreeNode* root,int distance){
        if (distance==0&&!visited.count(root->val)){
            ans.push_back(root->val);
            visited.insert(root->val);
        }
        else {
            if (root->left&&!visited.count(root->left->val)){
                findNodes(root->left,distance-1);
            }
            if (root->right&&!visited.count(root->right->val)){
                findNodes(root->right,distance-1);
            }
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

865. Smallest Subtree with all the Deepest Nodes

思路 DFS

在遍历时带有层数信息以及路径信息即可，通过DFS遍历获取最深层的节点以及其路径，然后通过从头到尾遍历确认那一层是最后的公共节点。

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    ArrayList<TreeNode> path = new ArrayList<>();
    int max_depth = 0;
    ArrayList<ArrayList<TreeNode>> res = new ArrayList<>();

    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        path.add(root);
        dfs(root, 1);
        if (res.size() == 1) {
            int len = res.get(0).size();
            return res.get(0).get(len - 1);
        }
        TreeNode prev = null;
        for (int i = 0; i < res.get(0).size(); i++) {
            int first = res.get(0).get(i).val;
            for (int j = 1; j < res.size(); j++) {
                if (res.get(j).get(i).val != first) {
                    return prev;
                }
            }
            prev = res.get(0).get(i);
        }
        return prev;
    }

    public void dfs(TreeNode node, int depth) {
        if (node.left == null && node.right == null) {
            if (depth < max_depth) {
                return;
            }
            if (depth > max_depth) {
                res.clear();
                max_depth = depth;
            }
            res.add(new ArrayList<>(path));
            return;
        }
        if (node.left != null) {
            path.add(node.left);
            dfs(node.left, depth + 1);
            path.remove(path.size() - 1);
        }
        if (node.right != null) {
            path.add(node.right);
            dfs(node.right, depth + 1);
            path.remove(path.size() - 1);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

919. Complete Binary Tree Inserter

思路 双队列

定义upper为上层还有子树空间的树节点队列，next为当前层树节点队列。例如在下图中，upper存储[2，3]，next存储[4]。

upper存储[3]，next存储[4]。

当树为完全二叉树时next队列为空，例如下面的情况中，upper存储[4,5,6,7],next为空：

在我们插入时，我们只需查看upper队列中是否还有元素，若有元素在upper中，则去除队列头节点，向其中插入新的树节点，并在next中加入子节点。如果该节点左右子节点插满，则upper移除该节点。
如果upper为空，则next成为新的upper、next为空。

代码

public class CBTInserter {
    Queue<TreeNode> upper;
    Queue<TreeNode> next;
    TreeNode root;

    public CBTInserter(TreeNode root) {
        upper = new LinkedList<>();
        next = new LinkedList<>();
        this.root = root;

        upper.offer(root);
        if (root.left != null) {
            next.offer(root.left);
        }
        if (root.right != null) {
            next.offer(root.right);
        }
        if (next.size()==2&&root.left.left==null){
            upper.clear();
            upper.addAll(next);
            next.clear();
        }
        while (!next.isEmpty() && next.peek().left != null) {
            int size = next.size();
            Queue<TreeNode> emptyQueue = new LinkedList<>();
            upper = emptyQueue;

            while (size > 0) {
                TreeNode node = next.poll();
                if (node.left != null) {
                    next.offer(node.left);
                }
                if (node.right != null) {
                    next.offer(node.right);
                }
                if (node.left == null || node.right == null) {
                    upper.offer(node);
                }
                size--;
            }
        }
    }

    public int insert(int val) {
        if (upper.isEmpty()) {
            refreshQueue();
        }
        TreeNode first = upper.peek();
        int parent_val = first.val;
        if (first.left == null) {
            first.left = new TreeNode(val);
            next.offer(first.left);
        } else {
            first.right = new TreeNode(val);
            next.offer(first.right);
            upper.poll();
        }
        return parent_val;
    }

    public TreeNode get_root() {
        return root;
    }

    public void refreshQueue() {
        upper = next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

**968. Binary Tree Cameras

思路 贪心+DFS+状态转移

这道题目其实不是那么好理解的，题目举的示例不是很典型，会误以为摄像头必须要放在中间，其实放哪里都可以只要覆盖了就行。

这道题目难在两点：

1. 需要确定遍历方式
2. 需要状态转移的方程

我们之前做动态规划的时候，只要最难的地方在于确定状态转移方程，至于遍历方式无非就是在数组或者二维数组上。

需要确定遍历方式

首先先确定遍历方式，才能确定转移方程，那么该如何遍历呢？

在安排选择摄像头的位置的时候，我们要从底向上进行推导，因为尽量让叶子节点的父节点安装摄像头，这样摄像头的数量才是最少的 ，这也是本道贪心的原理所在！

如何从低向上推导呢？

就是后序遍历也就是左右中的顺序，这样就可以从下到上进行推导了。

后序遍历代码如下：

    int traversal(TreeNode* cur) {

        // 空节点，该节点有覆盖
        if (终止条件) return ;

        int left = traversal(cur->left);    // 左
        int right = traversal(cur->right);  // 右

        逻辑处理                            // 中

        return ;
    }
1
2
3
4
5
6
7
8
9
10
11
12

注意在以上代码中我们取了左孩子的返回值，右孩子的返回值，即 left 和 right， 以后推导中间节点的状态

需要状态转移的方程

确定了遍历顺序，再看看这个状态应该如何转移，先来看看每个节点可能有几种状态：

可以说有如下三种：

1. 该节点无覆盖
2. 本节点有摄像头
3. 本节点有覆盖

那么问题来了，空节点究竟是哪一种状态呢？ 空节点表示无覆盖？ 表示有摄像头？还是有覆盖呢？

回归本质，为了让摄像头数量最少，我们要尽量让叶子节点的父节点安装摄像头，这样才能摄像头的数量最少。

那么空节点不能是无覆盖的状态，这样叶子节点就可以放摄像头了，空节点也不能是有摄像头的状态，这样叶子节点的父节点就没有必要放摄像头了，而是可以把摄像头放在叶子节点的爷爷节点上。

所以空节点的状态只能是有覆盖，这样就可以在叶子节点的父节点放摄像头了

接下来就是递推关系。

那么递归的终止条件应该是遇到了空节点，此时应该返回 2（有覆盖），原因上面已经解释过了。

        // 空节点，该节点有覆盖
        if (cur == NULL) return 2;
1
2

递归的函数，以及终止条件已经确定了，再来看单层逻辑处理。

主要有如下四类情况：

情况1：左右节点都有覆盖
左孩子有覆盖，右孩子有覆盖，那么此时中间节点应该就是无覆盖的状态了。

如图：

代码如下：

        // 左右节点都有覆盖
        if (left == 2 && right == 2) return 0;
1
2

情况2：左右节点至少有一个无覆盖的情况
如果是以下情况，则中间节点（父节点）应该放摄像头：

left == 0 && right == 0 - 左右节点无覆盖
left == 1 && right == 0- 左节点有摄像头，右节点无覆盖
left == 0 && right == 1- 左节点有无覆盖，右节点摄像头
left == 0 && right == 2 - 左节点无覆盖，右节点覆盖
left == 2 && right == 0 - 左节点覆盖，右节点无覆盖

这个不难理解，毕竟有一个孩子没有覆盖，父节点就应该放摄像头。

此时摄像头的数量要加一，并且 return 1，代表中间节点放摄像头。

代码如下：

        if (left == 0 || right == 0) {
            result++;
            return 1;
        }
1
2
3
4

情况3：左右节点至少有一个有摄像头
如果是以下情况，其实就是 左右孩子节点有一个有摄像头了，那么其父节点就应该是2（覆盖的状态）

left == 1 && right == 2 左节点有摄像头，右节点有覆盖
left == 2 && right == 1 左节点有覆盖，右节点有摄像头
left == 1 && right == 1 左右节点都有摄像头
代码如下：

        if (left == 1 || right == 1) return 2;
1

从这个代码中，可以看出，如果 left == 1, right == 0 怎么办？其实这种条件在情况 2 中已经判断过了，如图：

这种情况也是大多数同学容易迷惑的情况。
情况4：头结点没有覆盖
以上都处理完了，递归结束之后，可能头结点 还有一个无覆盖的情况，如图：

所以递归结束之后，还要判断根节点，如果没有覆盖，result++，代码如下：

    int minCameraCover(TreeNode* root) {
        result = 0;
        if (traversal(root) == 0) { // root 无覆盖
            result++;
        }
        return result;
    }
1
2
3
4
5
6
7
8
9

代码

class Solution {
private:
    int result;
    int traversal(TreeNode* cur) {

        // 空节点，该节点有覆盖
        if (cur == NULL) return 2;

        int left = traversal(cur->left);    // 左
        int right = traversal(cur->right);  // 右

        // 情况1
        // 左右节点都有覆盖
        if (left == 2 && right == 2) return 0;

        // 情况2
        // left == 0 && right == 0 左右节点无覆盖
        // left == 1 && right == 0 左节点有摄像头，右节点无覆盖
        // left == 0 && right == 1 左节点有无覆盖，右节点摄像头
        // left == 0 && right == 2 左节点无覆盖，右节点覆盖
        // left == 2 && right == 0 左节点覆盖，右节点无覆盖
        if (left == 0 || right == 0) {
            result++;
            return 1;
        }

        // 情况3
        // left == 1 && right == 2 左节点有摄像头，右节点有覆盖
        // left == 2 && right == 1 左节点有覆盖，右节点有摄像头
        // left == 1 && right == 1 左右节点都有摄像头
        // 其他情况前段代码均已覆盖
        if (left == 1 || right == 1) return 2;

        // 以上代码我没有使用else，主要是为了把各个分支条件展现出来，这样代码有助于读者理解
        // 这个 return -1 逻辑不会走到这里。
        return -1;
    }

public:
    int minCameraCover(TreeNode* root) {
        result = 0;
        // 情况4
        if (traversal(root) == 0) { // root 无覆盖
            result++;
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

987. Vertical Order Traversal of a Binary Tree

思路

用三个「哈希表」来记录相关信息：

使用node2row 和 node2col 分别用来记录「节点到行」&「节点到列」的映射关系，并实现 dfs1 对树进行遍历，目的是为了记录下相关的映射关系；

使用 col2row2nodes 记录「从列到行，从行到节点集」的映射关系，具体的存储格式为 {col : {row : [node1, node2, … ]}}，实现 dfs2 再次进行树的遍历，配合之前 node2row 和 node2col信息，填充 col2row2nodes 的映射关系；

按照题意，按「列号从小到大」，对于同列节点，按照「行号从小到大」，对于同列同行元素，按照「节点值从小到大」的规则，使用 col2row2nodes + 排序 构造答案。

代码

class Solution {
    Map<TreeNode, Integer> node2col = new HashMap<>(), node2row = new HashMap<>();
    Map<Integer, Map<Integer, List<Integer>>> col2row2nodes = new HashMap<>();
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        node2col.put(root, 0);
        node2row.put(root, 0);
        dfs1(root);
        dfs2(root);
        List<Integer> cols = new ArrayList<>(col2row2nodes.keySet());
        Collections.sort(cols);
        for (int col : cols) {
            Map<Integer, List<Integer>> row2nodes = col2row2nodes.get(col);
            List<Integer> rows = new ArrayList<>(row2nodes.keySet());
            Collections.sort(rows);
            List<Integer> cur = new ArrayList<>();
            for (int row : rows) {
                List<Integer> nodes = row2nodes.get(row);
                Collections.sort(nodes);
                cur.addAll(nodes);
            }
            ans.add(cur);
        }
        return ans;
    }
    // 树的遍历，根据「节点到列」&「节点到行」的映射关系，构造出「从列到行，从行到节点集」的映射关系
    void dfs2(TreeNode root) {
        if (root == null) return ;
        int col = node2col.get(root), row = node2row.get(root);
        Map<Integer, List<Integer>> row2nodes = col2row2nodes.getOrDefault(col, new HashMap<>());
        List<Integer> nodes = row2nodes.getOrDefault(row, new ArrayList<>());
        nodes.add(root.val);
        row2nodes.put(row, nodes);
        col2row2nodes.put(col, row2nodes);
        dfs2(root.left);
        dfs2(root.right);
    }
    // 树的遍历，记录下「节点到列」&「节点到行」的映射关系
    void dfs1(TreeNode root) {
        if (root == null) return ;
        if (root.left != null) {
            int col = node2col.get(root);
            node2col.put(root.left, col - 1);
            int row = node2row.get(root);
            node2row.put(root.left, row + 1);
            dfs1(root.left);
        }
        if (root.right != null) {
            int col = node2col.get(root);
            node2col.put(root.right, col + 1);
            int row = node2row.get(root);
            node2row.put(root.right, row + 1);
            dfs1(root.right);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

998. Maximum Binary Tree II

思路

大概意思是最大树 root 是根据特定的规则构造出来的，即给定的 root 其实对应一个具体的 nums，题目要求是将 val 追加到 nums 的尾部，然后再对得到的nums 运用相同规则的构造，返回重新构造的最大树头结点。

根据构造规则，若有下标 $i<j$，则 nums[i] 必然在 nums[j] 水平线的左边，而 val 又是追加在原有 nums 的结尾。因此其最终位置分如下两种情况：

1. val 为新 nums 中的最大值，同时val 又是追加在原有 nums 的结尾，此时将原有的 root 挂在 val 对应节点的左子树即可，新树的根节点为 val 对应节点；
2. 否则，我们只需要不断在 root 的右子树中找目标位置（反证法可以知，val 必不可能出现在任一非右位置，否则可推断出在 val 右边仍有元素，这与 val 位于 nums 的结尾位置冲突）。假设目标位置的父节点为 prev，目标位置的原节点为 cur，根据构造规则可知 prev.right = node 且 node.left = cur，新树的根节点不变。

代码

    public TreeNode insertIntoMaxTree(TreeNode root, int val) {
        if(root==null){
            return new TreeNode(val);
        }
        if(val>root.val){
            return new TreeNode(val,root,null);
        }
        root.right=insertIntoMaxTree(root.right,val);
        return root;
    }
1
2
3
4
5
6
7
8
9
10

*1008. Construct Binary Search Tree from Preorder Traversal

思路 递归

我们知道先序遍历的顺序是：根节点→左子树→右子树。二叉搜索树的特点是当前节点左子树的值都小于当前节点，当前节点右子树的值都大于当前节点。比如我们在下面的搜索二叉树中插入节点4.

使用递归的方式逐个插入即可。

1026. Maximum Difference Between Node and Ancestor

思路 DFS

使用TreeMap保存当前路径，每当遍历到路径尾时获取路径最大值最小值之差即可

代码

class Solution {
    int ans=0;
    TreeMap<Integer,Integer> path=new TreeMap<>();
    public int maxAncestorDiff(TreeNode root) {
        dfs(root);
        return ans;

    }
    public void dfs(TreeNode root){
        if (root==null){
            ans = Math.max(ans,path.lastKey()-path.firstKey());
            return;
        }
        path.merge(root.val,1,Integer::sum);
        dfs(root.left);
        dfs(root.right);
        path.merge(root.val,-1,Integer::sum);
        if (path.get(root.val)==0){
            path.remove(root.val);
        }
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

代码

class Solution {
    public TreeNode bstFromPreorder(int[] preorder) {
        TreeNode root=new TreeNode(preorder[0]);
        for (int i = 1; i < preorder.length; i++) {
            buildIterator(preorder[i],root);
        }
        return root;

    }
    public TreeNode buildIterator(int val,TreeNode root){
        if (root==null){
            return new TreeNode(val);
        }
        else if (root.val>val){
            root.left=buildIterator(val,root.left);
        }
        else{
            root.right=buildIterator(val,root.right);
        }
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

**1028. Recover a Tree From Preorder Traversal

思路 栈

初步思路

1. 连字符的个数代表节点的 level（深度）
2. 因为前序遍历 根∣左∣右根|左|右根∣左∣右，字符串开头的节点是根节点，后面的节点可以通过 level 找父亲：儿子的 level 要比父亲大 1，不满足就不是父亲
3. 当前节点的父亲，肯定在它的左边，从左往右扫描，儿子的父亲在左边，需要栈去记忆。

当前考察的节点，对应有 level

1. 节点有对应的 level，你可以用两个栈管理它们，其实也不用。
2. 扫描字符串时，每次考察一个节点，并算出它的 level，维护两个变量就行。

用栈去存储等待构建子树的节点

1. 当前节点的父亲不一定是它上一个节点，如下图。
2. 需要用一个栈，记忆左侧的节点（等着要构建子树的节点）
3. 节点入栈，等待自己子树的构建。构建完成的子树，出栈。

1. 当栈为空时，level 为 0 的根节点入栈，此时栈的 size 是 1
2. 入栈的节点的 level 如果是 1 ，等于栈的 size，则栈顶节点是它的父亲，就做它的儿子，而且尽量安排做左儿子
3. 它自己也要入栈，因为它自己也是父亲，等待自己的儿子，构建自己的子树

1. 如下图，如果栈的 size >>> 当前节点的 level
2. 说明栈顶节点不是当前节点的父亲，此时意味着栈顶节点的儿子已经找齐了（子树构建完毕），该出栈了。
3. 出栈，直到栈的 size 等于当前节点的 level，此时栈顶的节点就是当前节点的父亲。

留在栈中的都是缺儿子的

1. 子树构建完毕的节点会出栈，留在栈中的都是缺儿子的
2. 找到栈顶爸爸的节点，一定可以当儿子，当不了左儿子，就当右儿子

代码

    public TreeNode recoverFromPreorder(String _traversal) {
        char[] traversal=_traversal.toCharArray();
        Stack<TreeNode> stack=new Stack<>();
        for (int i = 0; i < traversal.length;) {
            int currLevel=0;
            while (i<traversal.length&&traversal[i]=='-'){
                currLevel++;
                i++;
            }
            int start=i;
            while (i<traversal.length&&traversal[i]!='-'){
                i++;
            }
            int val=Integer.parseInt(_traversal.substring(start,i));
            TreeNode node=new TreeNode(val);
            if (stack.isEmpty()){
                stack.push(node);
                continue;
            }
            while (stack.size()>currLevel){
                stack.pop();
            }
            if (stack.peek().left!=null){
                stack.peek().right=node;
            }
            else{
                stack.peek().left=node;
            }
            stack.push(node);
        }
        return stack.firstElement();
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

1123. Lowest Common Ancestor of Deepest Leaves(与865重复)

思路 DFS

同865

代码

同865

1448. Count Good Nodes in Binary Tree

思路 BFS

每次遍历时，带着先前节点的最大值。若当前节点值大于等于先前的最大值，则结果+1，并更新最大值。递归遍历其左右子节点。

代码

class Solution {
    int ans=0;
    public int goodNodes(TreeNode root) {
        goodNodesImpl(root,Integer.MIN_VALUE);
        return ans;
    }
    public void goodNodesImpl(TreeNode root,int prevMax){
        if (root==null){
            return;
        }
        if (prevMax<=root.val){
            ans++;
            prevMax=root.val;
        }
        goodNodesImpl(root.left,prevMax);
        goodNodesImpl(root.right,prevMax);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

1993. Operations on Tree

思路

逐个分析所需进行的操作：

lock & unlock
使用HashMap 做缓存即可
upgrade
因为upgrade需要确认parent以及children没有上锁，因此需要缓存一个children的HashMap用于存储每个节点的孩子。建立缓存后按照逻辑编写代码即可。

代码

class LockingTree {
    HashMap<Integer, Integer> locks = new HashMap<>();
    HashMap<Integer, ArrayList<Integer>> children = new HashMap<>();
    int[] parent;
    public LockingTree(int[] _parent) {
        parent=_parent;
        for (int i = 1; i < parent.length; i++) {
            if (!children.containsKey(parent[i])) {
                children.put(parent[i], new ArrayList<>());
            }
            children.get(parent[i]).add(i);
        }
    }

    public boolean lock(int num, int user) {
        if (locks.containsKey(num)) {
            return false;
        }
        locks.put(num, user);
        return true;
    }

    public boolean unlock(int num, int user) {
        if (locks.containsKey(num) && locks.get(num) == user) {
            locks.remove(num);
            return true;
        }
        return false;
    }

    public boolean upgrade(int num, int user) {
        if (!locks.containsKey(num)&&checkChildren(num)&&checkParent(num)){
            lock(num,user);
            Deque<Integer> subs = new LinkedList<>(children.get(num));
            while (!subs.isEmpty()) {
                var curr=subs.removeFirst();
                locks.remove(curr);
                if (children.containsKey(curr)){
                    subs.addAll(children.get(curr));
                }
            }
            return true;
        }
        return false;
    }

    public boolean checkChildren(int num) {
        if (!children.containsKey(num)) {
            return false;
        }
        Deque<Integer> subs = new LinkedList<>(children.get(num));
        while (!subs.isEmpty()) {
            var curr=subs.removeFirst();
            if (locks.containsKey(curr)){
                return true;
            }
            if (children.containsKey(curr)){
                subs.addAll(children.get(curr));
            }
        }
        return false;
    }
    public boolean checkParent(int num){
        while (parent[num]!=-1){
            num=parent[num];
            if (locks.containsKey(num)){
                return false;
            }
        }
        return !locks.containsKey(num);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

*2603 Distribute Coins in Binary Tree

思路 基于路径的DFS

问：根节点没有父节点，代码中为什么没有特判根节点呢？

答：根节点处统计的是整棵树，其中 coins=n,nodes=n\textit{coins}=n,\textit{nodes}=ncoins=n,nodes=n。因为 ∣coins−nodes∣=0|\textit{coins}-\textit{nodes}|=0∣coins−nodes∣=0，对答案无影响，所以无需特判根节点。

问：这种思路的本质是什么？

答：横看成岭侧成峰，每枚硬币移动的路径长度并不好计算，但是把这些路径叠起来，转换成每条边经过了多少枚硬币，就容易计算了（如下图）。

路径是由边组成的，所有路径长度之和，等同于把「每条边出现在多少条路径中」相加。这种技巧叫做贡献法。更多相关题目，见文末的题单。

代码

    int distributeCoins(TreeNode* root) {
        int ans=0;
        function<pair<int,int>(TreeNode*)> dfs=[&](TreeNode* root){
            if (root == nullptr){
                return make_pair(0,0);
            }
            auto [coins_l,nodes_l]=dfs(root->left);
            auto [coins_r,nodes_r]=dfs(root->right);
            int coins=coins_l+coins_r+root->val;
            int nodes=nodes_l+nodes_r+1;
            ans+= abs(coins-nodes);
            return make_pair(coins,nodes);
        };
        dfs(root);
        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16