关于程序员:宫水三叶的刷题日记1022-从根到叶的二进制数之和

6次阅读

共计 1879 个字符，预计需要花费 5 分钟才能阅读完成。

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

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

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

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

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

示例 1：

输出：root = [1,0,1,0,1,0,1]

输入：22

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

示例 2：

输出：root = [0]

输入：0

提醒：

树中的节点数在 $[1, 1000]$ 范畴内
Node.val 仅为 $0$ 或 $1$

容易想到「递归」进行求解，在 DFS 过程中记录下以后的值为多少，假如遍历到以后节点 $x$ 前，记录的值为 $cur$，那么依据题意，咱们须要先将 $cur$ 进行整体左移（腾出最初一位），而后将节点 $x$ 的值搁置最低位来失去新的值，并持续进行递归。

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

代码：

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

工夫复杂度：$O(n)$
空间复杂度：疏忽递归带来的额定空间开销，复杂度为 $O(1)$

天然也能够应用「迭代」进行求解。

为了不引入除「队列」以外的其余数据结构，当咱们能够把某个节点 $x$ 放出队列时，先将其的值批改为以后遍历门路对应的二进制数。

代码：

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