LeetCode刷题实战129：求根到叶子节点数字之和-技术圈

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 求根到叶子节点数字之和，我们先来看题面：

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

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

Note: A leaf is a node with no children.

题意

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

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

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

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

样例

解题

本体思路：采用层序遍历+递归的方法进行求解。

步骤一：构建递归函数（root代表当前根节点，number代表从根节点到当前节点的值）

步骤二：首先判断根节点是否有子节点，如果有，将根节点number*10+子节点的值放入新的递归函数中，直到所子节点遍历完毕，逐层返回所有值。

class Solution {
    public int sumNumbers(TreeNode root) {
          if(root==null) {
                return 0;
            }else {
                return getNumber(root,root.val);
            }
    }
   public int getNumber(TreeNode root,int number) {
        if(root.left==null&&root.right==null) {
            return number;
        }
        int templeft=0;
        int tempright=0;
        if(root.left!=null) {
            templeft=getNumber(root.left,root.left.val+number*10);
        }
        if(root.right!=null) {
            tempright=getNumber(root.right,root.right.val+number*10);
        }
        return templeft+tempright;
        
    } 
}