侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【递归, DFS, 位运算】从根到叶的二进制数之和

GabrielxD
2022-05-30 / 0 评论 / 0 点赞 / 28 阅读 / 452 字 / 正在检测是否收录...

题目

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


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

  • 例如,如果路径为 0 -> 1 -> 1 -> 0 -> 1,那么它表示二进制数 01101,也就是 13

对树上的每一片叶子,我们都要找出从根到该叶子的路径所表示的数字。

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

示例 1:

image-20220530001650148

输入: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 仅为 01

解题

方法一:递归 后序遍历 位运算

思路

后序遍历二叉树,遍历到每个节点:

  • 如果当前节点不为空就把从父节点拿到的值(num)左移一位再加上当前节点的值。
  • 如果当前节点是子节点,就把 num 加和到答案中,然后结束递归。
  • 递归左子节点,右子节点。

代码

class Solution {
    private int ans = 0;

    public int sumRootToLeaf(TreeNode root) {
        dfs(root, 0);
        return ans;
    }

    private void dfs(TreeNode root, int num) {
        if (root == null) return;
        num = (num << 1) + root.val;
        if (root.left == null && root.right == null) {
            ans += num;
            return;
        }
        dfs(root.left, num);
        dfs(root.right, num);
    }
}

优化

用加和返回值代替多维护的变量。

class Solution {
    public int sumRootToLeaf(TreeNode root) {
        return dfs(root, 0);
    }

    private int dfs(TreeNode root, int num) {
        if (root == null) return 0;
        num = (num << 1) + root.val;
        if (root.left == null && root.right == null) return num;
        return dfs(root.left, num) + dfs(root.right, num);
    }
}
0

评论区