栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

LeetCode 1022. 从根到叶的二进制数之和

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

LeetCode 1022. 从根到叶的二进制数之和

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

 

 

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/937160.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号