1022. 从根到叶的二进制数之和
【递归】 递归先序遍历
class Solution {
int ans = 0;
public void dfs(TreeNode node, int t){
if(node.left == null && node.right == null) {
t += node.val;
ans += t;
return;
}
t += node.val;
if(node.left != null) dfs(node.left, t << 1);
if(node.right != null) dfs(node.right, t << 1);
}
public int sumRootToLeaf(TreeNode root) {
dfs(root, 0);
return ans;
}
}
【递归】递归中序遍历,如果是null直接返回0,否则把上一层的t左移1位加上当前节点的值,如果当前是叶子结点直接返回这个值即可,否则递归遍历左右子树,返回左右子树的和。举个
1.开始跟节点1的时候t为0,t=0<<1|1=1,然后递归遍历他的儿子0和1;
2.左儿子0的时候,传过来的t为1,t=1<<1|0=10,然后递归遍历左儿子的左右儿子
(1)左儿子0,传来t=10,t=10<<1|0=100,由于左儿子已经是叶子,直接返回100
(2)右儿子1,传来t=10,t=10<<1|1=101,由于右儿子也是叶子,返回101
这样0的左右都会来了,0可以返回100+101
3.右儿子1的时候,传过来的t为1,t=1<<1|1=11,然后继续传t=11去遍历左右儿子0,1
得到左右儿子为110和111,1这个儿子返回110+111
这样跟节点的左右遍历玩了, 左返回100+101,右返回110+111,这样就把所有的值都加起来了。也就是说我们实际上还是遍历到叶子节点才返回路径上的总值,传进去的t相当于是个中间值,直到到了叶子结点才返回最终结果。
class Solution {
public int dfs(TreeNode node, int t){
if(node == null) return 0;
t = t << 1 | node.val;
if(node.left == null && node.right == null) return t;
int left = dfs(node.left, t);
int right = dfs(node.right, t);
return left + right;
}
public int sumRootToLeaf(TreeNode root) {
return dfs(root, 0);
}
}



