力扣每日一题2022-05-30简单题：从根到叶的二进制数之和

• • 题目描述
  • 思路
  • • 后序递归遍历
    • • Python实现
      • Java实现
      • C++实现

从根到叶的二进制数之和

后序遍历的访问顺序为左子树-右子树-根结点。对根节点进行后序遍历：

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

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
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)

class Solution {
    public int sumRootToLeaf(TreeNode root) {
        return dfs(root, 0);
    }

    private int dfs(TreeNode node, int val) {
        if (node == null) {
            return 0;
        }
        val = (val << 1) | node.val;
        if (node.left == null && node.right == null) {
            return val;
        }
        return dfs(node.left, val) + dfs(node.right, val);
    }
}

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