【Day 15 】2024-04-22 - 129. 求根到叶子节点数字之和

[azl397985856]

129. 求根到叶子节点数字之和

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/sum-root-to-leaf-numbers/

前置知识

• DFS
• BFS
• 前序遍历

  题目描述

  
  给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。

例如，从根到叶子节点路径 1->2->3 代表数字 123。

计算从根到叶子节点生成的所有数字之和。

说明: 叶子节点是指没有子节点的节点。

示例 1:

输入: [1,2,3] 1 / \ 2 3 输出: 25 解释: 从根到叶子节点路径 1->2 代表数字 12. 从根到叶子节点路径 1->3 代表数字 13. 因此，数字总和 = 12 + 13 = 25. 示例 2:

输入: [4,9,0,5,1] 4 / \ 9 0  / \ 5 1 输出: 1026 解释: 从根到叶子节点路径 4->9->5 代表数字 495. 从根到叶子节点路径 4->9->1 代表数字 491. 从根到叶子节点路径 4->0 代表数字 40. 因此，数字总和 = 495 + 491 + 40 = 1026.

[zhiyuanpeng]

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        ans = [0]
        self.dfs(root, 0, ans)
        return ans[0]

    def dfs(self, root, score, ans):
        score = score*10 + root.val
        if not root.left and not root.right:
            ans[0] += score
        else:
            if root.left:
                self.dfs(root.left, score, ans)
            if root.right:
                self.dfs(root.right, score, and)

time O(N) space O(logN)

[xil324]

/**

• @param {TreeNode} root

• @return {number} */ var sumNumbers = function(root) { let totalSum = 0; traveseToGetSum(root, []); return totalSum;

  function traveseToGetSum(node, path) { if(!node) return path.push(node.val) if(!node.left && !node.right) { totalSum += parseInt(path.join("")) } traveseToGetSum(node.left, path); traveseToGetSum(node.right, path); path.pop() } };

[JackinAI]

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

def sum_numbers(root): def dfs(node, current_number): if not node: return 0 current_number = current_number * 10 + node.val if not node.left and not node.right: return current_number return dfs(node.left, current_number) + dfs(node.right, current_number)

return dfs(root, 0)

root1 = TreeNode(1) root1.left = TreeNode(2) root1.right = TreeNode(3)

root2 = TreeNode(4) root2.left = TreeNode(9) root2.left.left = TreeNode(5) root2.left.right = TreeNode(1) root2.right = TreeNode(0)

print(sum_numbers(root1)) print(sum_numbers(root2)) `

[xy147]

js代码

var sumNumbers = function (nums) {
    let dfs = (node,pre)=>{
        if(!node) return 0
        const sum = pre * 10 + node.val
        if(node.left === null && node.right === null){
            return sum
        }
        return dfs(node.left,sum) + dfs(node.right,sum)
    }
    return dfs(root,0)
}

复杂度分析

• 时间复杂度: O(N)
• 空间复杂度: O(H)

[lxy1108]

思路

深度遍历树的同时记录经过的节点值，在遇到叶子节点时计算由该条路径构成的数字的值，最后返回所有数字的和

python3代码

class Solution:
    def dfs(self, node, path):
        path.append(node.val)
        if not node.left and not node.right:
            cur = 0
            for i in range(len(path)):
                cur += path[i] * (10**(len(path)-i-1))
            self.rs += cur
        if node.left:
            self.dfs(node.left, path)
        if node.right:
            self.dfs(node.right, path)
        path.pop()            

    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        self.rs = 0
        self.dfs(root, [])
        return self.rs

复杂度分析

时间复杂度O(n) 因为需要遍历树中的所有节点

空间复杂度O(n) 因为栈的深度取决于树的深度，在最坏情况下树的深度与节点个数相同

[CathyShang]

思路：

• 前序遍历 presum10+root->val;

代码：

class Solution {
public:
    int preOrder(TreeNode* root, int presum){
        if(root==nullptr) return 0;
        int sum = presum*10 + root->val;
        if(root->left==nullptr&&root->right==nullptr){
            return sum;
        }
        else {return preOrder(root->left, sum)+ preOrder(root->right, sum);
}
    }
    int sumNumbers(TreeNode* root) {
        return preOrder(root, 0);

    }
};

复杂度：

• 时间 $O(N)$ 遍历节点
• 空间 $O(H)$ 树的高度

[eclairs46]

思路

深度遍历

代码

var sumNumbers = function(root) {
    const recerve = (curRoot, sum) => {
        if(curRoot === null) {return 0}
        const curSum = sum * 10 + curRoot.val;
        if(curRoot.left === null && curRoot.right === null) { return curSum; }
        return recerve(curRoot.left, curSum) + recerve(curRoot.right, curSum)
    }
    return recerve(root, 0);
};

复杂度：

• 时间复杂度： O(n)
• 空间复杂度： O(h)

[hillsonziqiu]

思路

树的深度优先遍历后相加即可

代码

// 深度优先
const dfs = (root, pre) => {
  if (!root) return 0;

  let sum = pre * 10 + root.val;
  if (!root.left && !root.right) return sum;

  return dfs(root.left, sum) + dfs(root.right, sum);
};

/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumNumbers = function (root) {
  return dfs(root, 0);
};

复杂度分析

• 时间复杂度：O(n) 树的节点个数
• 空间复杂度：O(h) 树的高度

[YANGLimbo]

用了遍历的方法 在叶节点结算

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     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 {
protected:
    int _sum = 0;
public:
    void findLeafAndSumUp(TreeNode* root, int prev){
        if(root->left == nullptr && root->right == nullptr){
            // is leaf
            _sum += prev*10 + root->val;
            return;
        }

        if(root->left != nullptr){
            findLeafAndSumUp(root->left, prev*10 + root->val);
        }
        if(root->right != nullptr){
            findLeafAndSumUp(root->right, prev*10 + root->val);
        }

        return;
    }
    int sumNumbers(TreeNode* root) {
        findLeafAndSumUp(root,0);
        return _sum;
    }
};

[GReyQT]

代码：

class Solution {
public:
    int sumNumbersDeal(TreeNode* root, int lastSum) {
        if(root == nullptr)
        {
            return 0;
        }

        int sum = lastSum * 10 + root->val;
        if (root->left == nullptr && root->right == nullptr) 
        {
            return sum;
        } 
        else 
        {
            int left = sumNumbersDeal(root->left, sum);
            int right = sumNumbersDeal(root->right, sum);
            return left + right;
        }
    }
    int sumNumbers(TreeNode* root) 
    { 
        return sumNumbersDeal(root,0); 
    }
};

复杂度分析：

• 时间复杂度：时间的复杂度为O(n)
• 空间复杂度：空间复杂度为 O(n)

[Dtjk]

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

    void dfs(TreeNode* root, int num) {
        if (!root) return;
        if (!root->left && !root->right) {
            sum += num * 10 + root->val;
            return;
        }
        dfs(root->left, num * 10 + root->val);
        dfs(root->right, num * 10 + root->val);
    }
};

[atom-set]

思路

• 使用 dfs，每次 dfs 调用时候计算当前 curSum 的值
• 递归公式: dfs(root, 0) = dfs(root.left, curSum) + dfs(root.right, curSum)
  • curSum = curSum * 10 + root.val
• 退出条件：p 或者 q 有一个为 null 时，返回 sum 的和

代码

var sumNumbers = function (root) {
  var sum = 0;

  function dfs(root, cur) {
    if (!root) {
      return 0;
    }

    var curSum = cur * 10 + root.val;

    if (!root.left && !root.right) {
      sum += curSum;
      return;
    }

    dfs(root.left, curSum);
    dfs(root.right, curSum);
  }

  dfs(root, 0);
  return sum;
};

复杂度分析

递归需要遍历每个节点，故时间复杂度为 O(N) 递归调用的深度和树的高度有关，故空间复杂度为 O(H)

• 时间复杂度: O(N)
• 空间复杂度: O(H)

[Martina001]

时间复杂度: O(N) 空间复杂度: O(N)，最大的高度为节点个数，所以空间复杂度也是On

public int sumNumbers(TreeNode root) {
            // 这道题感觉像直接深度遍历拿到所有的值之后再相加比较简单 不过应该可以直接后续遍历边加和的吧 测试验证之后发现后序不对，改用前序
            // 这道题的重点在应该直接前序遍历保存当前已知的和preSum，然后preSum*10+子节点的数
            return dfs1(root,0);
        }
        private int dfs1(TreeNode root,int preSum){
            if(root == null){
                return 0;
            }
            int sum = preSum*10+root.val;
            // 如果叶子节点为空 就直接返回
            if(root.left == null && root.right == null){
                return sum;
            }else{
                //  获取叶子节点的和，左右叶子节点相加
                return dfs1(root.left,sum) + dfs1(root.right,sum);
            }
        }