【Day 15 】2023-02-28 - 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.

[bookyue]

TC: O(n)
SC: O(n)

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

    private int dfs(TreeNode root, int path) {
        if (root == null) return 0;

        path = path * 10 + root.val;
        if (root.left == null && root.right == null) return path;

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

[Manwzy]

/**

• Definition for a binary tree node.
• function TreeNode(val, left, right) {
• this.val = (val===undefined ? 0 : val)
• this.left = (left===undefined ? null : left)
• this.right = (right===undefined ? null : right)
• } */ /**
• @param {TreeNode} root
• @return {number} */

const traves = (root,arr,res)=>{ if(!root.left && !root.right){ arr.push(root.val) res.push(arr.reduce((sum,cur,index)=>{ sum+=cur*Math.pow(10,arr.length - index - 1) return sum },0)) arr.pop() return } arr.push(root.val) if(root.left){ traves(root.left,arr,res) } if(root.right){ traves(root.right,arr,res) } arr.pop() } var sumNumbers = function(root) { if(!root){ return 0 } let res = [] let arr = [] traves(root,arr,res) return res.reduce((sum,cur)=>{ sum+=cur return sum },0) };

[JiangyanLiNEU]

• DFS
• T = O(N) N is the number of nodes
• S = O(1)

  class Solution:
  def sumNumbers(self, root: Optional[TreeNode]) -> int:
      def dfs(head, prev):
          if not head:
              return prev
          if not head.left and not head.right:
              return prev*10 + head.val
          res = 0
          if head.left:
              res += dfs(head.left, prev*10+head.val)
          if head.right:
              res += dfs(head.right, prev*10+head.val)
          return res
      return dfs(root, 0)

• BFS
• T = O(N) N is the number of nodes
• S = O(N) N is the largest number of nodes in one layer

  class Solution:
  def sumNumbers(self, root: Optional[TreeNode]) -> int:
      branches = [root]
      res = 0
      while branches:
          temp = []
          for branch in branches:
              if not branch.left and not branch.right:
                  res += branch.val
              if branch.left:
                  branch.left.val = branch.val*10+branch.left.val
                  temp.append(branch.left)
              if branch.right:
                  branch.right.val = branch.val*10+branch.right.val
                  temp.append(branch.right)
          branches = temp
      return res

[Ryanbaiyansong]

Definition for a binary tree node.

class TreeNode:

def init(self, val=0, left=None, right=None):

self.val = val

self.left = left

self.right = right

class Solution: def sumNumbers(self, root: Optional[TreeNode]) -> int: s = 0 ans = 0 def dfs(root, cur): nonlocal ans if not root: return if not root.left and not root.right: ans += cur * 10 + root.val return

        dfs(root.left, cur * 10 + root.val)
        dfs(root.right, cur * 10 + root.val)

    dfs(root, 0)
    return ans

[zzhilin]

思路

• iteratively search through the tree
• use stack to get root and curr Number
• if at leaf, update curr else get left and right

代码

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        # iteratively search through the tree
        # use stack to get root and curr Number
        # if at leaf, update curr
        # else get left and right

        stack = [(root, 0)]
        total = 0

        while stack:
            node, curr = stack.pop()
            curr = curr * 10 + node.val

            if not node.left and not node.right:
                total += curr
            if node.left:
                stack.append((node.left, curr))
            if node.right:
                stack.append((node.right, curr))

        return total

复杂度分析 Time: O(N) all nodes in tree Space:O(H) height of tree

[kofzhang]

思路

深度优先搜索

复杂度

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

代码

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:

        def calcsub(node: Optional[TreeNode],current: int) -> int:            
            if not node:
                return 0
            s = current*10+node.val
            if not node.left and not node.right:                
                return s
            return calcsub(node.left,s)+calcsub(node.right,s)        

        return calcsub(root,0)

[Zoeyzyzyzy]

class Solution {
    // DFS: thinking of most easy case first: [1,2,3], and how to convey root.val *
    // 10 at each recursion
    // need have a parameter to record the sum before current tree node;
    // Be careful about a Tree only have left part / right part;
    // Time complexity:O(n), Space complexity O(n)
    int total = 0;

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

    private void dfs(TreeNode root, int pre) {
        if (root.left == null && root.right == null) {
            total += pre + root.val;
            return;
        }
        pre = (pre + root.val) * 10;
        if (root.left != null)
            dfs(root.left, pre);
        if (root.right != null)
            dfs(root.right, pre);
    }

    // BFS: use 2 queues to record node & value
    // Time Complexity: O(n), Space Complexity:O(n)
    public int sumNumbersBFS(TreeNode root) {
        if (root.left == null && root.right == null)
            return root.val;
        LinkedList<TreeNode> queue = new LinkedList<>();
        LinkedList<Integer> curValue = new LinkedList<>();
        queue.offer(root);
        curValue.offer(root.val);
        int sum = 0;
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            int curNum = curValue.poll();
            TreeNode left = cur.left, right = cur.right;
            if (left == null && right == null) {
                sum += curNum;
            } else {
                if (left != null) {
                    queue.offer(left);
                    curValue.offer(curNum * 10 + left.val);
                }
                if (right != null) {
                    queue.offer(right);
                    curValue.offer(curNum * 10 + right.val);
                }
            }
        }
        return sum;
    }

}

[mengsixing]

var sumNumbers = function(root) {
    return helper(root,0)
};

function helper(node,value){
    if(node === null){
        return 0;
    }
    let temp = value * 10 +  node.val;

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

    return helper(node.left,temp)+helper(node.right,temp)

}

[huizsh]

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumNumbers(root *TreeNode) int {
    return dfs(root, 0)
}

func dfs(root *TreeNode, cur int) int {
    if (root == nil) {
        return 0
    }
    if (root.Left == nil && root.Right == nil) {
        return cur*10 + root.Val
    }
    return dfs(root.Left, cur*10 + root.Val) + dfs(root.Right, cur*10 + root.Val)
}

[airwalkers]

class Solution {
    public int sumNumbers(TreeNode root) {
        if (root.left == null && root.right == null) {
            return root.val;
        }

        int ret = 0;

        if (root.left != null) {
            root.left.val += root.val * 10;
            ret += sumNumbers(root.left);
        }

        if (root.right != null) {
            root.right.val += root.val * 10;
            ret += sumNumbers(root.right);
        }

        return ret;
    }
}

[NorthSeacoder]

dfs

/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumNumbers = function(root) {
    const dfs = (node, sum) => {
        if (!node) return 0;
        sum = sum * 10 + node.val;
        if (!node.left && !node.right) return sum;
        return dfs(node.left, sum) + dfs(node.right, sum);
    };
    return dfs(root, 0);
};

• TC:O(n)

• SC: O(h)

  bfs

  /**
  * @param {TreeNode} root
  * @return {number}
  */
  var sumNumbers = function(root) {
  if (!root) return 0;
  const queue = [root];
  const valQueue = [root.val];
  
  let sum = 0;
  while (queue.length) {
      const node = queue.shift();
      const num = valQueue.shift();
      const {left, right} = node;
      if (!left && !right) {
          sum += num;
      } else {
          if (left) {
              queue.push(left);
              valQueue.push(left.val + num * 10);
          }
          if (right) {
              queue.push(right);
              valQueue.push(right.val + num * 10);
          }
      }
  }
  return sum;
  };

• TC:O(n)
• SC: O(n)

[duke-github]

思路

深度优先遍历 非叶子节点不处理

复杂度

时间复杂度O(n) 空间复杂度O(1)

代码

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

        public int getNum(TreeNode root, int val) {
            if (root == null) {
                return val;
            }
            if (root.left == null && root.right == null) {
                return val * 10 + root.val;
            }
            if (root.left == null) {
                return getNum(root.right, val * 10 + root.val);
            }
            if (root.right == null) {
                return getNum(root.left, val * 10 + root.val);
            }
            return getNum(root.left, val * 10 + root.val) + getNum(root.right, val * 10 + root.val);
        }
    }

[csthaha]

复杂度：

• 时间复杂度：O(n)

• 空间复杂度：O(m) m：路径

  代码：

  /**
  * Definition for a binary tree node.
  * function TreeNode(val, left, right) {
  *     this.val = (val===undefined ? 0 : val)
  *     this.left = (left===undefined ? null : left)
  *     this.right = (right===undefined ? null : right)
  * }
  */
  /**
  * @param {TreeNode} root
  * @return {number}
  */
  var sumNumbers = function(root) {
  const list = [];
  
  const help = (root, path) => {
      if(!root) return;
      path += root.val
      if(!root.left && !root.right) {
          list.push(path)
          return;
      };
      help(root.left,  path)
      help(root.right, path)
  }
  help(root, '');
  return list.reduce((a, b) => (a + (+b)), 0)
  };

[tzuikuo]

思路

递归，遍历

代码

class Solution {
public:
    int curnum=0,sum=0;
    int sumNumbers(TreeNode* root) {
        traversal(root);

        return sum;
    }
    void traversal(TreeNode* cur){
        curnum=curnum*10+cur->val;
        if(cur->left) traversal(cur->left);
        if(cur->right) traversal(cur->right);
        if(!cur->left&&!cur->right){
            sum+=curnum;
        }
        curnum=(curnum-cur->val)/10;
        return;
    }
};

复杂度分析

• 时间 O(N)
• 空间 O(N)

[KrabbeJing]

思路

DFS

代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        def dfs(root, cur):
            if root is None:
                return 0
            if root.left is None and root.right is None:
                return cur * 10 + root.val
            return dfs(root.left, cur*10+root.val) + dfs(root.right, cur*10+root.val)

        return dfs(root, 0)

复杂度

时间复杂度O(节点数)

空间复杂度O(高度)

[chanceyliu]

代码

export class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
}

function sumNumbers(root: TreeNode | null): number {
  // 结果
  let result: number = 0;
  // 临时数组
  let temp: number[] = [];

  const dfs = (node: TreeNode | null) => {
    if (!node) {
      return;
    }
    // 判断叶子节点，进行求和赋值
    if (!node.left && !node.right) {
      const strSum = temp.join("") + `${node.val}`;
      const numSum = Number(strSum);
      result += numSum;
      return;
    }
    // 普通节点纳入数组
    temp.push(node.val);
    if (node.left) {
      dfs(node.left);
    }
    if (node.right) {
      dfs(node.right);
    }
    // 只有当左右节点已经计算完成的时候，才进行回溯
    temp.pop();
  };

  dfs(root);

  return result;
}

复杂度分析

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

[Fuku-L]

代码

1. DFS：深度优先遍历，每次递归时，需要把当前计算的值传到下一个节点。

   class Solution {
   public int sumNumbers(TreeNode root) {
       return dfs(root, 0);
   }
   public int dfs(TreeNode root, int preNum){
       if(root == null){
           return 0;
       }
       int sum = root.val + preNum * 10;
       if(root.left == null && root.right == null){
           // 根节点
           return sum;
       } else {
           return dfs(root.right, sum) + dfs(root.left, sum);
       }
   }
   }

2. BFS：广度优先遍历，需要使用两个队列记录待遍历的节点以及遍历值的情况。如果当前节点的左子树和右子树为空，那么将当前值加到求和中，如果某个子树不为空，需要将该节点入队，并将当前值*10+节点值入队。

   class Solution {
   public int sumNumbers(TreeNode root) {
       if(root == null){
           return 0;
       }
       Queue<TreeNode> nodeQ = new LinkedList<>();
       Queue<Integer> numQ = new LinkedList<>();
       nodeQ.offer(root);
       numQ.offer(root.val);
       int sum = 0;
       while(!nodeQ.isEmpty()){
           TreeNode cur = nodeQ.poll();
           int num = numQ.poll();
           TreeNode left = cur.left;
           TreeNode right = cur.right;
           if(left == null && right == null){
               sum += num;
           } else{
               if(left != null){
                   nodeQ.offer(left);
                   numQ.offer(left.val + num * 10);
               }
               if(right != null){
                   nodeQ.offer(right);
                   numQ.offer(right.val + num * 10);
               }
           }
       }
       return sum;
   }
   }

   复杂度分析

   • 时间复杂度：O(N)，其中 N 为数组长度。
   • 空间复杂度：O(N)

[kyo-tom]

思路

dfs 遍历

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int sumNumbers(TreeNode root) {
            return getNum(root, 0);
        }

        // val 为到当前位置的路径上所经历的节点的综合
        public int getNum(TreeNode root, int val) {
            if (root.left == null && root.right == null) {
                return val * 10 + root.val;
            }
            if (root.left == null) {
                return getNum(root.right, val * 10 + root.val);
            }
            if (root.right == null) {
                return getNum(root.left, val * 10 + root.val);
            }
            return getNum(root.left, val * 10 + root.val) + getNum(root.right, val * 10 + root.val);
        }
}

复杂度分析

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

[FireHaoSky]

思路：

''' 采用递归，分别遍历节点，并且将根节点的值传入 '''

解题：python

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        def dfs(root:Optional[TreeNode], prevale:int) -> int:
            if not root:
                return 0

            cal = prevale * 10 + root.val
            if not root.left and not root.right:
                return cal

            else:
                return dfs(root.left, cal) + dfs(root.right, cal)

        return dfs(root,0)

复杂度分析：

''' 时间复杂度：O(n) 空间复杂度：O(n) '''

[Meisgithub]

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

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

            // num = num * 10 + root->val;
            // cout << num << endl;
            sum += num;
            // num /= 10;
            // return;
        }
        // num = num * 10 + root->val;
        dfs(root->left,  num, sum);
        dfs(root->right,  num, sum);
        // sum += num;
        // cout << num << endl;
        num /= 10;
    }
};

[954545647]

思路

递归出口为叶子节点：当前节点的左右节点均为 null

代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumNumbers = function (root) {
  const helper = (root, cur) => {
    if (root === null) return 0;
    cur = 10 * cur + root.val;
    if (root.left === null && root.right === null) return cur;
    return helper(root.left, cur) + helper(root.right, cur);
  };
  return helper(root, 0);
};

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(N)

[Abby-xu]

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        p = {root: root.val}
        c = dict()
        res = 0
        while p:
            for node, number in p.items():
                if node.left:
                    c[node.left] = number*10 + node.left.val
                if node.right:
                    c[node.right] = number*10 + node.right.val
                if not node.left and not node.right:
                    res += number
            p = c
            c = dict()
        return res

[linlizzz]

思路

每下一层，前面的数字扩大10倍

代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        def dfs(root, pre):
            if root == None:
                return 0
            total = pre*10 + root.val
            if root.left == None and root.right == None:
                return total
            else:
                return dfs(root.left, total) + dfs(root.right, total)
        return dfs(root, 0)

复杂度分析

T(n) = O(n), n为节点数

S(n) = O(n)

[Leonalhq]

 思路

（此处撰写思路）

 代码

class Solution(object):
    def sumNumbers(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        return self.dfs(root, 0)

    def dfs(self, root, now):
        if not root: 
            return 0
        if not root.left and not root.right:
            return now * 10 + root.val

        return self.dfs(root.left, now*10 +root.val) + self.dfs(root.right, now*10 +root.val)

**复杂度分析**  
- 时间复杂度：O(N)
- 空间复杂度：O(logN)

[GuitarYs]

Definition for a binary tree node.

class TreeNode:

def init(self, val=0, left=None, right=None):

self.val = val

self.left = left

self.right = right

class Solution: def sumNumbers(self, root: Optional[TreeNode]) -> int: def dfs(root, pre): if root == None: return 0 total = pre*10 + root.val if root.left == None and root.right == None: return total else: return dfs(root.left, total) + dfs(root.right, total) return dfs(root, 0)

[yfu6]

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        root_to_leaf = 0
        stack = [(root, 0) ]

        while stack:
            root, curr_number = stack.pop()
            if root is not None:
                curr_number = curr_number * 10 + root.val
                if root.left is None and root.right is None:
                    root_to_leaf += curr_number
                else:
                    stack.append((root.right, curr_number))
                    stack.append((root.left, curr_number))

        return root_to_leaf

[wangqianqian202301]

思路

1. 遍历二叉树， 构造出所有结点的前结点， 存在hash中
2. 对当前位做加法

3. 合并最终结果

   代码

   
   class Solution:
   def sumNumbers(self, root: Optional[TreeNode]) -> int:
               if root is None:
           return 0
       preHash = {}
       list = []
       toAdd = []
       list.append(root)
       while list:
           e = list.pop()
           if e.left:
               list.append(e.left)
               preHash[e.left] = e
           if e.right:
               list.append(e.right)
               preHash[e.right] = e
   
           if e.left is None and e.right is None:
               toAdd.append(e)
   
       result = []
   
       temp = 0
       while toAdd:
           preNodeArr = []
           for n in toAdd:
               temp = temp + n.val
               if preHash[n]:
                   preNodeArr.append(preHash[n])
           result.append(temp % 10)
           temp = temp // 10
           toAdd = preNodeArr
       if temp > 0:
           result.append(temp)
   
       sum = 0
       while result:
           sum = sum * 10 + result.pop()
   
       return sum

##### 复杂度
O(n)
O(n)

[X1AOX1A]

0129. 求根节点到叶节点数字之和

题目

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字：

例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
计算从根节点到叶节点生成的 所有数字之和 。

叶节点 是指没有子节点的节点。

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

思路：DFS

• 使用字符串 num 储存向下过程中的 数字
• 但触及底部时，将数字 num 加入sum，并删去最后一位 num[:-1]，回溯

代码

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:

        def dfs(node, num, Sum):
            if not node: return Sum
            if not node.left and not node.right: 
                num += str(node.val)
                Sum += int(num)
                num = num[:-1]
            else:
                num += str(node.val)          
                Sum = dfs(node.left, num, Sum)
                Sum = dfs(node.right, num, Sum)
            return Sum  

        return dfs(root, "", 0)

• 时间复杂度：O(n)，遍历所有点
• 空间复杂度：O(h)，递归过程中的stack，h 为树的高度
• 时间 24 ms 击败 99.64%
• 内存 14.9 MB 击败 63.95%

[chocolate-emperor]

class Solution {
public:
    int dfs(TreeNode*curr, int num){
        if(curr->left==nullptr && curr->right==nullptr) {
            return  num*10+ curr->val;
        }
        int res = 0;
        if(curr->left)  res+=dfs(curr->left,num*10+curr->val);
        if(curr->right) res+=dfs(curr->right,num*10+curr->val);
        return res;
    }
    int sumNumbers(TreeNode* root) {
        return dfs(root,0);
    }
};

[jmaStella]

思路

DFS base case: 只有一个node，value = root.val recursive case: preorder 一直把前面算好的数字传下去，到leafnode 算好穿回来

代码

public int sumNumbers(TreeNode root) {
        if(root == null){
            return 0 ;
        }
        return helper(root,0); 

    }
    public int helper(TreeNode root, int pVal){

        if(root.left == null && root.right == null){
            return pVal*10 +root.val;
        }
        int left = 0;
        int right =0;
        if(root.left != null){
            left = helper(root.left, pVal*10+root.val);
        }
        if(root.right != null){
            right = helper(root.right, pVal*10+root.val);
        }

        return left +right;

    }

复杂度

时间：O(N) 空间：O(h)

[FlipN9]

// TC: O(n), SC: O(h)
class Solution {
    int total = 0;

    public int sumNumbers(TreeNode root) {
        traverse(root, 0);
        return total;
    }

    private void traverse(TreeNode root, int curSum) {
        if (root == null) return;
        curSum = curSum * 10 + root.val;
        if (root.left == null && root.right == null) {
            total += curSum;
            return;
        }
        traverse(root.left, curSum);
        traverse(root.right, curSum);
    }
}

[harperz24]

class Solution:
    def __init__(self, root_to_leaf=0):
        self.root_to_leaf = root_to_leaf

    def preorder(self, root: TreeNode, cur: int) -> None:
        # base case
        if not root:
            return

         # update the current sum
        cur = cur * 10 + root.val

        # if node is a leaf node, add the current sum to the total sum
        if not root.left and not root.right:
            self.root_to_leaf += cur

        # recurse on the left subtree and right subtree
        self.preorder(root.left, cur)
        self.preorder(root.right, cur)

    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        self.preorder(root, 0)
        return self.root_to_leaf

    # dfs, preorder tranveral
    # time: O(n) 
    # space: O(h)

[huifeng248]

##### i will update the thought process later on 

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        def dfs(root, cur):
            if not root:
                return 0

            cur = cur * 10 + root.val

            if not root.left and not root.right:
                return cur

            return dfs(root.left, cur) + dfs(root.right, cur)

        return dfs(root, 0)

# Time Complexity : O(N), where N is the number of nodes in the tree. We are doing a standard DFS traversal which takes O(N) time
# Space Complexity : O(H), where H is the maximum depth of tree. This space is required for implicit recursive stack space. In the worst case, the tree maybe skewed and H = N in which case space required is equal to O(N).

[wangzh0114]

思路

• 递归

  代码

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

private: int helper(const TreeNode root, int _val){ if(!root) return 0; int ret = root->val + _val 10; if(!root->left && !root->right) return ret; int l = helper(root->left, ret); int r = helper(root->right, ret); return l + r; } };

---
### 复杂度分析
- TC:O(N)
- SC:O(N)

[Horace7]

const sumNumbers = (root) => {
  const helper = (root, cur) => {
    if (root == null) {
      return 0;
    }
    cur = 10 * cur + root.val;
    if (root.left == null && root.right == null) {
      return cur;
    }
    return helper(root.left, cur) + helper(root.right, cur);
  };
  return helper(root, 0);
};

[zcytm3000]

class Solution: def sumNumbers(self, root: TreeNode) -> int: def dfs(root: TreeNode, prevTotal: int) -> int: if not root: return 0 total = prevTotal * 10 + root.val if not root.left and not root.right: return total else: return dfs(root.left, total) + dfs(root.right, total)

    return dfs(root, 0)

[hshen202108]

题目地址(129. 求根节点到叶节点数字之和)

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

题目描述

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。

每条从根节点到叶节点的路径都代表一个数字：

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

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

叶节点 是指没有子节点的节点。

 

示例 1：

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

示例 2：

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

 

提示：

树中节点的数目在范围 [1, 1000] 内
0 <= Node.val <= 9
树的深度不超过 10

前置知识

公司

• 暂无

思路

关键点

代码

• 语言支持：Java

Java Code:

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

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

    public void dfs(TreeNode root, int last){
        if(root == null) return;
        if(root.left == null && root.right == null) {
            ans += last * 10 + root.val;
            return;
        }
        dfs(root.left, last * 10 + root.val);
        dfs(root.right, last * 10 + root.val);
    }
}

复杂度分析

令 n 为数组长度。 令 n 为节点总数， h 为树的高度。

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

[luckyoneday]

代码

var sumNumbers = function(root) {
  return dfs(root, '');

  function dfs(root, prefix) {
    if (!root) return 0;
    const newP = prefix + root.val;
    if (!root.left && !root.right) {
      return newP;
    }

    const left = dfs(root.left, newP);
    const right = dfs(root.right, newP); 

    return +left + +right;
  }
};

[AstrKing]

思路

求从根到叶子的路径之和，那我们只需要把每条根到叶子的路径找出来，并求和即可，这里用 DFS 去解，DFS 也是最容易想到的。

代码

    public int sumNumbers(TreeNode root) {
        return helper(root, 0);
    }

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

复杂度分析

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

[Elsa-zhang]

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        def dfs(root, cur):
            if not root:
                return 0
            if not root.left and not root.right:
                return cur*10+root.val
            return dfs(root.left, cur*10+root.val) + dfs(root.right, cur*10+root.val)

        return dfs(root, 0)

[yuzmt]

思路

深度优先搜索

代码

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

复杂度

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

[Bochengwan]

思路

DFS, 递归过程中传递之前的sum

代码

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

    }

    public int dfs(TreeNode currNode, int prevSum) {
        if (currNode == null) return 0;
        prevSum = prevSum*10 + currNode.val;
        if (currNode.left == null && currNode.right == null) return prevSum;

        return dfs(currNode.left, prevSum) + dfs(currNode.right, prevSum);
    }
}

复杂度分析

• 时间复杂度：O(N)，其中 N 为树的节点个数
• 空间复杂度：O(H)， h为树的高度，最差为O（n）

[xiaoq777]

class Solution {
    int result = 0;

    public int sumNumbers(TreeNode root) {
        sum(root, 0);
        return result;
    }

    public void sum(TreeNode node, int num) {
        if(node == null) {
            return;
        }
        if(node.left == null && node.right == null) {
            result += num * 10 + node.val;
        }else {
            num = num * 10 + node.val;
            sum(node.left, num);
            sum(node.right, num);
        }
    }
}

[JasonQiu]

• DFS

  class Solution:
  def sumTree(self, root, prefix):
      prefix = prefix * 10 + root.val
      left = self.sumTree(root.left, prefix) if root.left else 0
      right = self.sumTree(root.right, prefix) if root.right else 0
      sum = left + right
      return sum if sum > 0 else prefix
  
  def sumNumbers(self, root: Optional[TreeNode]) -> int:
      return self.sumTree(root, 0)

  Time: O(n) Space: O(n)

[C2tr]

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

    def dfs(root, cur):
        if not root:
            return 0

        cur = cur * 10 + root.val

        if not root.left and not root.right:
            return cur

        return dfs(root.left, cur) + dfs(root.right, cur)

    return dfs(root, 0)

[KangQinSen]

题目地址(129. 求根节点到叶节点数字之和)

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

前置知识

二叉树的遍历-深度遍历

思路

前序搜索的关键点

关键点

代码

• 语言支持：Java

Java Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int sum = 0 ; 
    public int sumNumbers(TreeNode root) {
      if(root == null ){
        return 0 ; 
      }
      dfs(root , 0);
      return sum;
    }
    private void dfs(TreeNode root , int val){
      val*=10;
      val+=root.val;
      if(root.left == null && root.right == null){
        sum+=val;
      }
      if(root.left != null){
        dfs(root.left , val);
      }
      if(root.right != null){
        dfs(root.right , val);
      }
    }
}

复杂度分析

令 n 为数组长度。

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

[CruiseYuGH]

思路

关键点

• dfs

代码

• 语言支持：Python3

Python3 Code:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        #dfs
        def dfs(root,presum):
            if root is None:
                return 0
            presum = presum*10 +root.val
            if root.left is None and root.right is None:
                return presum
            return dfs(root.left,presum) + dfs(root.right,presum)
        return dfs(root,0)

复杂度分析

令 n 为数组长度。

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

[kangliqi1]

class Solution { public int sumNumbers(TreeNode root) { if (root.left == null && root.right == null) { return root.val; } int ret = 0; if (root.left != null) { root.left.val += root.val 10; ret += sumNumbers(root.left); } if (root.right != null) { root.right.val += root.val 10; ret += sumNumbers(root.right); } return ret; } }

[liuajingliu]

解题思路

DFS

代码实现

javaScript

/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
  if(!p && !q) return true
  if(!p || !q) return false;
  if(p.val != q.val) return false;

  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
};

复杂度分析

• 时间复杂度 $O(N)$
• 空间复杂度 $O(N)$

[RestlessBreeze]

code

/**
 * 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 {
public:

    int sum1(int a, TreeNode* root)
    {
        int b = 10 * a + root->val;
        if (!root->left && !root->right) return b;
        else if (!root->left && root->right) return sum1(b, root->right);
        else if (root->left && !root->right) return sum1(b, root->left);
        else return sum1(b, root->left) + sum1(b, root->right);
    }

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