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

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

leetcode 链接

解法一：递归 + 进制转换

初始化结果为 0,深度优先遍历二叉树，记录 path，到叶子节点时，结果加上 path 转化为十进制的数值，最后返回。

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function sumRootToLeaf(root: TreeNode | null): number {
  let res = 0;
  const dfs = (tree: TreeNode, path: string) => {
    if (tree == null) return;
    const newPath = `${path}${tree.val}`;
    if (!tree.left && !tree.right) {
      res += parseInt(newPath, 2);
      return;
    }
    dfs(tree.left, newPath);
    dfs(tree.right, newPath);
  };
  dfs(root, "");
  return res;
}

解法二：递归 + 位运算

同样是深度优先遍历，与解法一不同的是不用记录结果和 path

dfs 时结果传递给下一次递归，由于每一次是二进制位最后加上 0 或 1

所以可以使用 << 运算符，时使操作数左移 1 位（即 val << 1）

左移一位后，二进制最后一位便补了 0，然后再使用 | 操作符，时结果加上当前节点的值。

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function sumRootToLeaf(root: TreeNode | null): number {
  const dfs = (tree: TreeNode, val: number): number => {
    if (!tree) return 0;
    const tmpVal = (val << 1) | tree.val;
    if (!tree.left && !tree.right) {
      return tmpVal;
    }
    return dfs(tree.left, tmpVal) + dfs(tree.right, tmpVal);
  };
  return dfs(root, 0);
}

:::info << 左移操作符即把左边的操作数（转换成二进制后）左移 n 位，左边超出的位数会被清除，右边补 0，比如：

2 << 2 意思是把 2 左移 2 位

0010; // 移动前 2
1000; // 移动两位后 8

a << b 等于 a * 2 ** b :::