leetcode算法【129】求根到叶子节点数字之和

r囧r小猫 2022-11-28 13:59 270阅读 0赞

文章目录

        • 所有题目源代码：[Git地址](https://github.com/ch98road/leetcode)
        • 题目
        • 方案：
          • 复杂度计算

所有题目源代码：Git地址

题目

  1. 给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。
  3. 例如，从根到叶子节点路径 1->2->3 代表数字 123。
  5. 计算从根到叶子节点生成的所有数字之和。
  7. 说明: 叶子节点是指没有子节点的节点。
  9. 示例 1:
  11. 输入: [1,2,3]
  12.     1
  13.    / \
  14.   2   3
  15. 输出: 25
  16. 解释:
  17. 从根到叶子节点路径 1->2 代表数字 12.
  18. 从根到叶子节点路径 1->3 代表数字 13.
  19. 因此，数字总和 = 12 + 13 = 25.
  20. 示例 2:
  22. 输入: [4,9,0,5,1]
  23.     4
  24.    / \
  25.   9   0
  26.  / \
  27. 5   1
  28. 输出: 1026
  29. 解释:
  30. 从根到叶子节点路径 4->9->5 代表数字 495.
  31. 从根到叶子节点路径 4->9->1 代表数字 491.
  32. 从根到叶子节点路径 4->0 代表数字 40.
  33. 因此，数字总和 = 495 + 491 + 40 = 1026.

方案：

  • 前序遍历+计数

    /* Definition for a binary tree node. public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } */
    class Solution { 

    1. private int sum = 0;
    2. public int sumNumbers(TreeNode root) { 
    3.     //遍历导叶子节点，加到sum
    4.     if(root==null){ 
    5.         return 0;
    6.     }
    7.     if(root.right==null&&root.left==null){ 
    8.         return root.val;
    9.     }
    10.     if(root.left!=null){ 
    11.         find_leaf(root.left,root.val*10);
    12.     }
    13.     if(root.right!=null){ 
    14.         find_leaf(root.right,root.val*10);
    15.     }
    16.     return sum;
    18. }
    19. public void find_leaf(TreeNode root,int num){ 
    20.     num +=root.val;
    21.     //找到叶子节点
    22.     if(root.left==null&&root.right==null){ 
    23.         sum += num;
    24.     }
    25.     if(root.left!=null){ 
    26.         find_leaf(root.left,num*10);
    27.     }
    28.     if (root.right!=null){ 
    29.         find_leaf(root.right,num*10);
    30.     }
    31. }

    }

复杂度计算
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

发表评论

表情：
评论列表 （有 0 条评论，270人围观）

还没有评论，来说两句吧...

相关阅读