Java算法题-解析根到叶子节点数字之和问题

题目

在这个算法题中，我们将解决如何计算根到叶子节点路径表示的数字之和的问题。每个节点都包含一个数字，路径表示的数字是从根节点到叶子节点的数字拼接而成的。

引言

计算根到叶子节点数字之和需要一种递归的方法，该方法可以遍历二叉树的所有路径，并将每条路径表示的数字进行累加。在递归遍历二叉树时，需要传递当前节点的值和已经累加的数字。

算法思路

1. 使用深度优先搜索（DFS）遍历二叉树。
2. 在递归遍历的过程中，传递当前节点的值和已经累加的数字。
3. 如果当前节点是叶子节点，则将已累加的数字与当前节点的值相加，得到一条完整的路径表示的数字，并将其累加到总和中。
4. 如果当前节点不是叶子节点，则递归遍历其左子树和右子树，将当前节点的值传递给下一层递归。

代码实现

以下是使用 Java 实现的解决方案：

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

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

        currentSum = currentSum * 10 + node.val;

        if (node.left == null && node.right == null) {
            return currentSum;
        }

        int leftSum = dfs(node.left, currentSum);
        int rightSum = dfs(node.right, currentSum);

        return leftSum + rightSum;
    }
}

算法分析

• 时间复杂度：遍历二叉树的每个节点一次，时间复杂度为 O(N)，其中 N 是二叉树的节点数。
• 空间复杂度：递归调用的栈空间深度取决于二叉树的高度，空间复杂度为 O(H)，其中 H 是二叉树的高度。

示例和测试

我们可以使用以下代码进行测试：

public class Main {
    public static void main(String[] args) {
        SumRootToLeafNumbers solution = new SumRootToLeafNumbers();

        // 构建二叉树
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        int sum = solution.sumNumbers(root);
        System.out.println("根到叶子节点数字之和: " + sum); // 输出 262 + 251 = 513
    }
}

总结

计算根到叶子节点数字之和是一个递归遍历二叉树的问题，通过深度优先搜索，我们可以高效地计算出每条路径表示的数字，并将其累加得到总和。这个问题的时间复杂度是 O(N)，空间复杂度是 O(H)，其中 N 是二叉树的节点数，H 是二叉树的高度。理解递归的应用对于解决类似的问题非常有帮助。