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

我们先来看题目描述在二维平面上的 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 。如果节点是非叶子节点返回它的左子树和右子树对应的结果之和。代码Python3class 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) JavaCclass 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); } };Cint 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); }