【Day 15】129. 求根到叶子节点数字之和.md

思路

每个节点对应的数字等于其父节点对应数字乘以10再加上当前节点的数字，dfs遍历每一个节点，直至节点为null则返回。

代码

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

    public int dfs(TreeNode root, int num){
        if(root == null) return 0;
        int temp = num * 10 + root.val;
        if(root.left == null && root.right == null){
            return temp;
        }else{
            return dfs(root.left, temp) + dfs(root.right, temp);
        }
    }
}

复杂度分析

• 时间复杂度：O(n)，遍历每一个节点。
• 空间复杂度：O(n)，递归深度为树的高度，最大为n。