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

题目

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

---

给出一棵二叉树，其上每个结点的值都是 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

解题

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

思路

后序遍历二叉树，遍历到每个节点：

• 如果当前节点不为空就把从父节点拿到的值(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);
    }
}