129.路径总和从根到叶

标签: tree, depth-first-search, binary-search-tree

难度: Medium

通过率: 67.37%

原题链接: https://leetcode.com/problems/sum-root-to-leaf-numbers/description/

题目描述

给定一个只包含数字0到9的二叉树，每条从根到叶的路径都代表一个数字。返回所有根到叶路径数字的总和。

解题思路

要解决这个问题，我们需要遍历二叉树的每一条从根节点到叶节点的路径，并计算这些路径所表示的数字的总和。可以采用递归的方式进行深度优先搜索（DFS），在遍历的过程中逐步构建每条路径对应的数字。在每一步，将经过的节点的值与当前的数字进行组合，例如当前的数字为current，节点值为node.val，那么新的数字就是 current * 10 + node.val。递归到叶节点时，将计算出的数字加入总和。

代码实现

Python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def sumNumbers(root):
    # 定义一个递归函数，用于遍历树
    def dfs(node, current_sum):
        if not node:
            return 0

        # 更新当前路径的数字
        current_sum = current_sum * 10 + node.val

        # 如果到达叶节点，返回当前完整的路径数字
        if not node.left and not node.right:
            return current_sum

        # 递归计算左子树和右子树的路径数字总和
        left_sum = dfs(node.left, current_sum)
        right_sum = dfs(node.right, current_sum)

        return left_sum + right_sum

    return dfs(root, 0)

C++

class TreeNode {
public:
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        return dfs(root, 0);
    }

private:
    int dfs(TreeNode* node, int current_sum) {
        if (node == nullptr) return 0;

        // 更新当前路径的数字
        current_sum = current_sum * 10 + node->val;

        // 如果到达叶节点，返回当前完整的路径数字
        if (node->left == nullptr && node->right == nullptr) {
            return current_sum;
        }

        // 递归计算左子树和右子树的路径数字总和
        return dfs(node->left, current_sum) + dfs(node->right, current_sum);
    }
};

JavaScript

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

var sumNumbers = function(root) {
    const dfs = (node, current_sum) => {
        if (!node) return 0;

        // 更新当前路径的数字
        current_sum = current_sum * 10 + node.val;

        // 如果到达叶节点，返回当前完整的路径数字
        if (!node.left && !node.right) {
            return current_sum;
        }

        // 递归计算左子树和右子树的路径数字总和
        return dfs(node.left, current_sum) + dfs(node.right, current_sum);
    };
    
    return dfs(root, 0);
};

Java

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

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

    private int dfs(TreeNode node, int current_sum) {
        if (node == null) return 0;

        // 更新当前路径的数字
        current_sum = current_sum * 10 + node.val;

        // 如果到达叶节点，返回当前完整的路径数字
        if (node.left == null && node.right == null) {
            return current_sum;
        }

        // 递归计算左子树和右子树的路径数字总和
        return dfs(node.left, current_sum) + dfs(node.right, current_sum);
    }
}

复杂度分析

时间复杂度：$O(N)$，其中 $N$ 是树中节点的数目。我们需要遍历每个节点。 空间复杂度：最坏情况下是 $O(H)$，其中 $H$ 是树的高度，考虑到递归调用栈的深度。