宫水三叶的刷题日记

V1

2022/06/18阅读:13主题:前端之巅同款

【宫水三叶的刷题日记】1022. 从根到叶的二进制数之和

题目描述

这是 LeetCode 上的 1022. 从根到叶的二进制数之和 ,难度为 简单

Tag : 「DFS」、「BFS」、「二叉树」、「树的遍历」

给出一棵二叉树,其上每个结点的值都是   或   。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。

例如,如果路径为 0 -> 1 -> 1 -> 0 -> 1,那么它表示二进制数 01101,也就是   。 对树上的每一片叶子,我们都要找出从根到该叶子的路径所表示的数字。

返回这些数字之和。题目数据保证答案是一个 位 整数。

示例 1:

输入:root = [1,0,1,0,1,0,1]

输出:22

解释:(100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22

示例 2:

输入:root = [0]

输出:0

提示:

  • 树中的节点数在   范围内
  • Node.val 仅为

递归

容易想到「递归」进行求解,在 DFS 过程中记录下当前的值为多少,假设遍历到当前节点 前,记录的值为 ,那么根据题意,我们需要先将 进行整体左移(腾出最后一位),然后将节点 的值放置最低位来得到新的值,并继续进行递归。

递归有使用「函数返回值」和「全局变量」两种实现方式。

代码:

class Solution {
    public int sumRootToLeaf(TreeNode root) {
        return dfs(root, 0);
    }
    int dfs(TreeNode root, int cur) {
        int ans = 0, ncur = (cur << 1) + root.val;
        if (root.left != null) ans += dfs(root.left, ncur);
        if (root.right != null) ans += dfs(root.right, ncur);
        return root.left == null && root.right == null ? ncur : ans;
    }
}
class Solution {
    int ans = 0;
    public int sumRootToLeaf(TreeNode root) {
        dfs(root, 0);
        return ans;
    }
    void dfs(TreeNode root, int cur) {
        int ncur = (cur << 1) + root.val;
        if (root.left != null) dfs(root.left, ncur);
        if (root.right != null) dfs(root.right, ncur);
        if (root.left == null && root.right == null) ans += ncur;
    }
}
  • 时间复杂度:
  • 空间复杂度:忽略递归带来的额外空间开销,复杂度为

迭代

自然也可以使用「迭代」进行求解。

为了不引入除「队列」以外的其他数据结构,当我们可以把某个节点 放出队列时,先将其的值修改为当前遍历路径对应的二进制数。

代码:

class Solution {
    public int sumRootToLeaf(TreeNode root) {
        int ans = 0;
        Deque<TreeNode> d = new ArrayDeque<>();
        d.addLast(root);
        while (!d.isEmpty()) {
            TreeNode poll = d.pollFirst();
            if (poll.left != null) {
                poll.left.val = (poll.val << 1) + poll.left.val;
                d.addLast(poll.left);
            }
            if (poll.right != null) {
                poll.right.val = (poll.val << 1) + poll.right.val;
                d.addLast(poll.right);
            }
            if (poll.left == null && poll.right == null) ans += poll.val;
        }
        return ans;
    }
}
  • 时间复杂度:
  • 空间复杂度:

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1022 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

分类:

后端

标签:

数据结构与算法

作者介绍

宫水三叶的刷题日记
V1