📑 题目：129. 求根节点到叶节点数字之和

🚀 本题 LeetCode 传送门

题目大意

给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。例如，从根到叶子节点路径 1->2->3 代表数字 123。计算从根到叶子节点生成的所有数字之和。说明: 叶子节点是指没有子节点的节点。

解题思路

  • 这一题是第 257 题的变形题，第 257 题要求输出每条从根节点到叶子节点的路径，这一题变成了把每一个从根节点到叶子节点的数字都串联起来，再累加每条路径，求出最后的总和。实际做题思路基本没变。运用前序遍历的思想，当从根节点出发一直加到叶子节点，每个叶子节点汇总一次。

代码

  1. package leetcode
  3. import (
  4.  ""github.com/halfrost/LeetCode-Go/structures""
  5. )
  7. // TreeNode define
  8. type TreeNode = structures.TreeNode
  10. /**
  11.  * Definition for a binary tree node.
  12.  * type TreeNode struct {
  13.  *     Val int
  14.  *     Left *TreeNode
  15.  *     Right *TreeNode
  16.  * }
  17.  */
  19. func sumNumbers(root *TreeNode) int {
  20.  res := 0
  21.  dfs(root,0,&res)
  22.  return res
  23. }
  25. func dfs(root *TreeNode,sum int,res *int)  {
  26.  if root == nil{
  27.   return
  28.  }
  29.  sum = sum*10 + root.Val
  30.  if root.Left == nil && root.Right == nil{
  31.   *res += sum
  32.   return
  33.  }
  34.  dfs(root.Left,sum,res)
  35.  dfs(root.Right,sum,res)
  36. }