1. Toy模板网首页
  2. > Toy博客

算法刷题记录-树(LeetCode)

10月前 作者：ほしのした 分类：Toy博客 阅读(46) 违法举报

这篇具有很好参考价值的文章主要介绍了算法刷题记录-树(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);
    }
};

814. Binary Tree Pruning

思路(DFS)

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

863. All Nodes Distance K in Binary Tree

思路（DFS）

首先，需要通过dfs算法找到从原点到目标点的路径。 p a t h = [ 2 , 3 , 5 , 7 ] path=[2,3,5,7] path=[2,3,5,7], k = 2 k=2 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);
            }
        }
    }
};

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);
        }
    }
}

919. Complete Binary Tree Inserter

思路 双队列

定义upper为上层还有子树空间的树节点队列，next为当前层树节点队列。例如在下图中，upper存储[2，3]，next存储[4]。
算法刷题记录-树(LeetCode),算法,算法,leetcode,深度优先
upper存储[3]，next存储[4]。
算法刷题记录-树(LeetCode),算法,算法,leetcode,深度优先

当树为完全二叉树时next队列为空，例如下面的情况中，upper存储[4,5,6,7],next为空：
算法刷题记录-树(LeetCode),算法,算法,leetcode,深度优先
在我们插入时，我们只需查看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;
    }
}

**968. Binary Tree Cameras

思路 贪心+DFS+状态转移

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

这道题目难在两点：

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

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

需要确定遍历方式

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

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

如何从低向上推导呢？

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

后序遍历代码如下：

    int traversal(TreeNode* cur) {

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

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

        逻辑处理                            // 中

        return ;
    }

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

需要状态转移的方程

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

可以说有如下三种：

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

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

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

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

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

接下来就是递推关系。

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

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

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

主要有如下四类情况：

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

如图：
算法刷题记录-树(LeetCode),算法,算法,leetcode,深度优先
代码如下：

        // 左右节点都有覆盖
        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 - 左节点覆盖，右节点无覆盖

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

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

代码如下：

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

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

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

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

从这个代码中，可以看出，如果 left == 1, right == 0 怎么办？其实这种条件在情况 2 中已经判断过了，如图：
算法刷题记录-树(LeetCode),算法,算法,leetcode,深度优先
这种情况也是大多数同学容易迷惑的情况。
情况4：头结点没有覆盖
以上都处理完了，递归结束之后，可能头结点 还有一个无覆盖的情况，如图：
算法刷题记录-树(LeetCode),算法,算法,leetcode,深度优先
所以递归结束之后，还要判断根节点，如果没有覆盖，result++，代码如下：



    int minCameraCover(TreeNode* root) {
        result = 0;
        if (traversal(root) == 0) { // root 无覆盖
            result++;
        }
        return result;
    }

代码

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;
    }
};

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);
        }
    }
}

998. Maximum Binary Tree II

思路

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

根据构造规则，若有下标 i < j i<j 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;
    }

*1008. Construct Binary Search Tree from Preorder Traversal

思路 递归

我们知道先序遍历的顺序是：根节点→左子树→右子树。二叉搜索树的特点是当前节点左子树的值都小于当前节点，当前节点右子树的值都大于当前节点。比如我们在下面的搜索二叉树中插入节点4.
算法刷题记录-树(LeetCode),算法,算法,leetcode,深度优先
算法刷题记录-树(LeetCode),算法,算法,leetcode,深度优先

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

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);
        }
    }

}

代码

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;
    }
}

**1028. Recover a Tree From Preorder Traversal

思路 栈

初步思路

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

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

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

算法刷题记录-树(LeetCode),算法,算法,leetcode,深度优先
用栈去存储等待构建子树的节点

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

算法刷题记录-树(LeetCode),算法,算法,leetcode,深度优先

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

算法刷题记录-树(LeetCode),算法,算法,leetcode,深度优先

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

算法刷题记录-树(LeetCode),算法,算法,leetcode,深度优先

留在栈中的都是缺儿子的

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

算法刷题记录-树(LeetCode),算法,算法,leetcode,深度优先

代码

    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();
    }

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);
    }
}

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);
    }
}

*2603 Distribute Coins in Binary Tree

思路 基于路径的DFS

算法刷题记录-树(LeetCode),算法,算法,leetcode,深度优先
问：根节点没有父节点，代码中为什么没有特判根节点呢？

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

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

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

算法刷题记录-树(LeetCode),算法,算法,leetcode,深度优先
路径是由边组成的，所有路径长度之和，等同于把「每条边出现在多少条路径中」相加。这种技巧叫做贡献法。更多相关题目，见文末的题单。文章来源地址https://www.toymoban.com/news/detail-702117.html

代码

    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;
    }

到了这里，关于算法刷题记录-树(LeetCode)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【深度优先】【广度优先】Leetcode 104 二叉树的最大深度 Leetcode 111 二叉树的最小深度 Leetcode 110 平衡二叉树

    【深度优先】【广度优先】Leetcode 104 二叉树的最大深度 Leetcode 111 二叉树的最小深度 Leetcode 110 平衡二叉树

    二叉树节点的深度： 指从根节点到该节点的最长简单路径边的条数或者节点数 （取决于深度从0开始还是从1开始） 二叉树节点的高度： 指从该节点到叶子节点的最长简单路径边的条数后者节点数 （取决于高度从0开始还是从1开始） 【前序求的是深度，后序求的是高度】 -

    2024年02月19日
    浏览(52)
  • 【LeetCode刷题记录】数组专题

    【LeetCode刷题记录】数组专题

    说明 ： 文章内容为个人的力扣刷题记录，不定时更新。 文章内容如有错误，欢迎指正。 2023-04-24 题目1. 两数之和 1. 两数之和 - 力扣（Leetcode） 方法一：暴力解法，循环遍历 C++ python 方法二：哈希表 参考1. 两数之和 - 力扣（Leetcode） 哈希表的查找时间复杂度为O(1)，可以大大

    2024年02月02日
    浏览(58)

  • python LeetCode 刷题记录 13

    题号：13 罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。 字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000 例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。 通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特

    2024年02月08日
    浏览(41)

  • python LeetCode 刷题记录 28

    给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

    2024年02月08日
    浏览(61)

  • LeetCode刷题记录--- 微软企业题库

    😄 今天是2022年12月30号，我开始了LeetCode的《微软企业题库》专题 刷题！ 😄 开了力扣plus会员了，可以看到各企业的出题情况和题目的出现频率，所以打算把各企业的出题指数第一页 (也就是top50题刷一遍)，当然肯定有些题也是刷过的，那就当二刷。加油！ 🚀 进度： 已完

    2024年02月08日
    浏览(42)

  • LeetCode-200. 岛屿数量【深度优先搜索 广度优先搜索 并查集 数组 矩阵】

    给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 此外，你可以假设该网格的四条边均被水包围。 示例 1： 输入：grid = [ [“1”,“1”,“1”,“

    2024年04月14日
    浏览(39)
  • C++ 之LeetCode刷题记录（十七）

    C++ 之LeetCode刷题记录（十七）

    😄😊😆😃😄😊😆😃 开始cpp刷题之旅。 依旧是追求耗时0s的一天。 给你一个二叉树的根节点 root ， 检查它是否轴对称。 示例 1： 输入：root = [1,2,2,3,4,4,3] 输出：true 示例 2： 输入：root = [1,2,2,null,3,null,3] 输出：false 这题目感觉还是比较简单的 先看根节点是否相同，再判断

    2024年01月25日
    浏览(48)
  • C++ 之LeetCode刷题记录（十二）

    C++ 之LeetCode刷题记录（十二）

    😄😊😆😃😄😊😆😃 开始cpp刷题之旅。 依旧是追求耗时0s的一天。 示例 1： 输入：x = 4 输出：2 示例 2： 输入：x = 8 输出：2 解释：8 的算术平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。 思路：这种题目一看就是二分法，很简单的题目，耗时0s，看代码。

    2024年01月18日
    浏览(56)

  • LeetCode刷题记录——day1

    https://leetcode.cn/problems/h-index/description/?envType=study-plan-v2envId=top-interview-150 注：题目有点难理解，多读几遍 可以这样考虑，建立另一个临时数组 temp ，当第 i 篇文章被引用 citiations[i] 次时，令 j=citiations[i] 的 temp[j] 均加一，也就是现在对于任意 j 至少有 temp[j] 篇论文引用次数大

    2024年03月18日
    浏览(38)

  • LeetCode刷题记录——day2

    https://leetcode.cn/problems/product-of-array-except-self/description/?envType=study-plan-v2envId=top-interview-150 问题在于不使用除法并且空间复杂度为 O(1) ，当第一次从头开始遍历时由于不知道后续数组元素是什么，所以无法得到答案，而如果当知道一个后续数组元素后，又回去更新答案的话，无

    2024年03月20日
    浏览(79)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包