经典算法实例：从根到叶的二进制数之和

我们先来看题目描述：

在二维平面上的 x 轴上，放置着一些方块。

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

解决方案

方法：递归

后序遍历的访问顺序为：左子树——右子树——根节点。我们对根节点 root 进行后序遍历：

如果节点是叶子节点，返回它对应的数字 val 。
如果节点是非叶子节点，返回它的左子树和右子树对应的结果之和。

代码

Python3

class Solution: def sumRootToLeaf(self, root: Optional[TreeNode]) -> int: def dfs(node: Optional[TreeNode], val: int) -> int: if node is None: return 0 val = (val << 1) | node.val if node.left is None and node.right is None: return val return dfs(node.left, val) + dfs(node.right, val) return dfs(root, 0) Java

C++

class Solution { public: int dfs(TreeNode *root, int val) { if (root == nullptr) { return 0; } val = (val << 1) | root->val; if (root->left == nullptr && root->right == nullptr) { return val; } return dfs(root->left, val) + dfs(root->right, val); } int sumRootToLeaf(TreeNode* root) { return dfs(root, 0); } };

C

int dfs(struct TreeNode *root, int val) { if (root == NULL) { return 0; } val = (val << 1) | root->val; if (root->left == NULL && root->right == NULL) { return val; } return dfs(root->left, val) + dfs(root->right, val); } int sumRootToLeaf(struct TreeNode* root){ return dfs(root, 0); }