X

LEETCODE 1022. Sum of Root To Leaf Binary Numbers 解题思路分析

题目大意:

从根到叶的二进制数之和

给出一棵二叉树,其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。例如,如果路径为 0 -> 1 -> 1 -> 0 -> 1,那么它表示二进制数 01101,也就是 13 。

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

以 10^9 + 7 为模,返回这些数字之和。

示例:

输入:[1,0,1,0,1,0,1]
输出:22
解释:(100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22

提示:

  1. 树中的结点数介于 11000 之间。
  2. node.val 为 01

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1022

解题思路分析:

解法一:

本题可以利用dfs遍历出从顶点到所有叶子节点的路径。理论上,每存在一个叶子节点,就会对应一条路径。由于dfs遍历不会出现重复路径,因此,每一条路径对应的数字相加即是结果。对于任意一个非叶子节点,他都会出现1或者2条分支,当前节点下,所有分支的和应该等于左子节点的和加上右子节点的和(如果某一个子节点为空,则它的和为0)。

看下详细代码:

public int sumRootToLeaf(TreeNode root) {
    return dfs(root, 0);
}
// root为当前节点。
// sum为根节点到当前节点父节点之和
// 返回值为当前节点下所有线路的和
int dfs(TreeNode root, int sum){
    // 由于节点的值代表2进制的当前位,因此到当前位的和应该为:
    // 高位和乘以2再加上当前位。
    sum = (sum*2+root.val);
    // 如果为叶子节点,直接返回sum。
    if(root.left == null && root.right==null){
        return sum;
    }
    int res=0; // 定义返回值。
    if(root.left != null){
        // 左子节点不为空,递归计算左子节点下所有线路的和
        res+=dfs(root.left, sum);
    }
    if(root.right != null){
        // 右子节点不为空,递归计算右子节点下所有线路的和
        res+=dfs(root.right, sum);
    }
    return res;
}

解法二:

解法二实际上与解法一没有本质的区别,不过个人认为更好理解一点。我们定义一个全局变量res,作为返回结果,累加每一条路径的数值。还是利用dfs遍历每一条路径,每到达一个节点,我们计算出根节点到当前节点的和,如果当前节点为叶子节点,那么就将本路径的和加到res中,否则继续向下dfs。

看下代码:

public int sumRootToLeaf(TreeNode root) {
    dfs(root, 0);
    return res;
}
int res=0; // 返回结果
// root为当前节点。
// sum为根节点到当前节点父节点之和
void dfs(TreeNode root, int sum){
    // 由于节点的值代表2进制的当前位,因此到当前位的和应该为:
    // 高位和乘以2再加上当前位。
    sum = sum * 2 + root.val;
    // 如果是叶子节点,将结果加入res
    if(root.left==null && root.right==null){
        res+=sum;
        return;
    }
    // 向下dfs(递归)左子节点
    if(root.left != null){
        dfs(root.left, sum);
    }
    // 向下dfs(递归)右子节点
    if(root.right != null){
        dfs(root.right, sum);
    }
}

本解法用时0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Sum of Root To Leaf Binary Numbers.

Memory Usage: 36.9 MB, less than 100.00% of Java online submissions for Sum of Root To Leaf Binary Numbers.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-1022-sum-of-root-to-leaf-binary-numbers-解题思路分析/
Categories: leetcode
kwantong: