讨论/《深度优先搜索》 - 例题:求根到叶子节点数字之和/
《深度优先搜索》 - 例题:求根到叶子节点数字之和
共 4 个回复
class Solution {
public:
    int sumNumbers(TreeNode* root) {
        return dfs(root,0);
    }
    int dfs(TreeNode*node,int preVal){//函数功能:返回此节点的 值
        if(node==NULL) return 0;
        if(node->left==NULL&&node->right==NULL) return node->val+preVal*10;
        return dfs(node->left, node->val+preVal*10)+dfs(node->right, node->val+preVal*10);
    }
};
class Solution {
    int res = 0;
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }
    private int dfs(TreeNode node, int sum){
        if(node == null) return 0;
        sum = sum * 10 + node.val;
        if(node.left == null && node.right == null){
            return sum; 
        }
        return dfs(node.left, sum) + dfs(node.right, sum);
    }
}

C++ implementation

class Solution {
public:
    int dfs(TreeNode* root){
        if(root==NULL)
            return 0;
        if(root->left==NULL && root->right==NULL)
            return root->val;
        //update values for its children
        if(root->left!=NULL){
            root->left->val=root->val*10+root->left->val;
        }
        if(root->right!=NULL){
            root->right->val=root->val*10+root->right->val;
        }
        return dfs(root->left)+dfs(root->right);
    }

    int sumNumbers(TreeNode* root) {
        return dfs(root);
    }
};
print('Hello world!')
puts 'Hello world!'
class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        if not root :return 0
        res = 0 
        def dfs(root,pth):
            nonlocal res
            if not root.left and not root.right:
                res += reduce(lambda x,y:10 * x + y,pth+[root.val])
            else:
                if root.left : dfs(root.left,pth+[root.val])
                if root.right : dfs(root.right,pth+[root.val])
        dfs(root,[])
        return res