Using recursive function inside to make a Depth fisrt search, visiting the outer variable, solving the "979. Distribute Coins in Binary Tree".
Recursive funciton inside
how to visit the outer variable in the inside function.
const d = () {};(function d(){})()var d func() int
d = func() int {}$d = fn() => ''lambdaFunction = () -> ''lambdaFuncion = () => ''function <int()> d [&]()->int {}ans = [0] #Python 2
def d():
ans[0] += 1
return ans[0]ans = 0 #Python 3
def d():
nonlocal ans
ans += 1
return ansvoid d(){}
void (*funcPtr)() = &d;
funcPtr();Example
979. Distribute Coins in Binary Tree
You are given the root of a binary tree with n nodes where each node in the tree has node.val coins. There are n coins in total throughout the whole tree.
In one move, we may choose two adjacent nodes and move one coin from one node to another. A move may be from parent to child, or from child to parent.
Return the minimum number of moves required to make every node have exactly one coin.
Example 1:
Input: root = [3,0,0]
Output: 2
Explanation: From the root of the tree, we move one coin to its left child, and one coin to its right child.
Answers
Depth first search using recursive function inside
var distributeCoins = function(root) {
let ans = 0
const d = root => {
if (root === null) return 0
const l = d(root.left), r = d(root.right)
ans += Math.abs(l) + Math.abs(r)
return l + r + root.val - 1
}
return d(root), ans
};function distributeCoins(root: TreeNode | null): number {
let ans = 0
;(function d(root) {
if (root === null) return 0
const l = d(root.left), r = d(root.right)
ans += Math.abs(l) + Math.abs(r)
return l + r + root.val - 1
})(root)
return ans
};func distributeCoins(root *TreeNode) int {
ans := 0
var d func(*TreeNode) int
d = func(root *TreeNode) int {
if root == nil {
return 0
}
l, r := d(root.Left), d(root.Right)
ans += int(math.Abs(float64(l)) + math.Abs(float64(r)))
return l + r + root.Val - 1
}
d(root)
return ans
}class Solution {
private $ans = 0;
function distributeCoins($root) {
$this->d($root);
return $this->ans;
}
function d($root) {
if ($root === null) return 0;
$l = $this->d($root->left);
$r = $this->d($root->right);
$this->ans += abs($l) + abs($r);
return $l + $r + $root->val - 1;
}
}class Solution {
private int ans = 0;
public int distributeCoins(TreeNode root) {
d(root);
return ans;
}
public int d(TreeNode root) {
if (root == null) return 0;
int l = d(root.left), r = d(root.right);
ans += Math.abs(l) + Math.abs(r);
return l + r + root.val - 1;
}
}public class Solution {
private int ans = 0;
public int DistributeCoins(TreeNode root) {
d(root);
return ans;
}
public int d(TreeNode root) {
if (root == null) return 0;
int l = d(root.left), r = d(root.right);
ans += Math.Abs(l) + Math.Abs(r);
return l + r + root.val - 1;
}
}class Solution {
public:
int distributeCoins(TreeNode* root) {
int ans = 0;
function<int(const TreeNode*)> d = [&](const TreeNode* root) -> int {
if (root == nullptr) return 0;
int l = d(root->left), r = d(root->right);
ans += abs(l) + abs(r);
return l + r + root->val - 1;
};
d(root);
return ans;
}
};int d(struct TreeNode* root, int* ans) {
if (root == NULL) return 0;
int l = d(root->left, ans), r = d(root->right, ans);
(*ans) += abs(l) + abs(r);
return l + r + root->val - 1;
}
int distributeCoins(struct TreeNode* root){
int ans = 0;
d(root, &ans);
return ans;
}class Solution(object): # Python2
def distributeCoins(self, root):
ans = [0]
def d(root):
if root == None: return 0
l, r = d(root.left), d(root.right)
ans[0] += abs(l) + abs(r)
return l + r + root.val - 1
d(root)
return ans[0]class Solution: # Python3
def distributeCoins(self, root: Optional[TreeNode]) -> int:
ans = 0
def d(root):
nonlocal ans
if root == None: return 0
l, r = d(root.left), d(root.right)
ans += abs(l) + abs(r)
return l + r + root.val - 1
d(root)
return ans
