树

题解-每棵子树内缺失的最小基因值

一个树上操作的问题的解法

题解-有向图访问计数,一个有向基环树的简单应用

一个有向基环树的性质问题,帮助快速理解环的性质和意义

题解-在二叉树中分配硬币-深度优先搜索,自底向上考虑

Problem: 979. 在二叉树中分配硬币 思路 考虑最后计算成本的时候实际上是计算的是每个节点对硬币的操作数 每个节点只需要一个硬币,如何确定多出来的或少的硬币的流向 考虑自底向上,叶子节点只需要一个硬币,这样就能向父节点要硬币或者向父节点送硬币,之后父节点变成了叶子节点(其子节点已完成使命) 设一个值为$Need$表示需要向上移或者向上要的硬币数,根据以上推论我们能够得到如下公式,正数表示需要向上移动,负数表示需要上方向下移动 $$Need_{节点}=Need_{子节点}+val-1$$ 每次将一个节点处理完就将Need的绝对值加入到操作数之中 Code class Solution: def distributeCoins(self, root: Optional[TreeNode]) -> int: self.res=0 def dfs(node:TreeNode): if node==None: return 0 left=dfs(node.left) right=dfs(node.right) self.res+=abs(left)+abs(right) return right+left+node.val-1 dfs(root) return self.res class Solution { public: int res=0; int dfs(TreeNode* root){ if (!root) return 0; int left=dfs(root->left); int right=dfs(root->right); res+=abs(left)+abs(right); return left+right+root->val-1; } int distributeCoins(TreeNode* root) { dfs(root); return res; } };