首页 > 代码库 > 【LeetCode-面试算法经典-Java实现】【129-Sum Root to Leaf Numbers(全部根到叶子结点组组成的数字相加)】

【LeetCode-面试算法经典-Java实现】【129-Sum Root to Leaf Numbers(全部根到叶子结点组组成的数字相加)】

【129-Sum Root to Leaf Numbers(全部根到叶子结点组组成的数字相加)】


【LeetCode-面试算法经典-Java实现】【全部题目文件夹索引】

原题

  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.
  For example,

    1
   /   2   3

  The root-to-leaf path 1->2 represents the number 12.
  The root-to-leaf path 1->3 represents the number 13.
Return the sum = 12 + 13 = 25.

题目大意

  给定一个二叉树。每一个结点的值是0-9。根到叶子组成一个数字,求全部的根到叶子组成的数字的和。

解题思路

  採用回溯法。


代码实现

算法实现类

public class Solution {

    private int result = 0; // 记录总的结果
    private int num = 0; // 记根到叶子的数字

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

    private void sum(TreeNode root) {
        if (root != null) {
            num = num*10 + root.val;

            // 已经到了根结点了
            if (root.left == null && root.right == null) {
                result += num;
            }
            sum(root.left);
            sum(root.right);
            num /= 10;
        }
    }
}

评測结果

  点击图片,鼠标不释放,拖动一段位置,释放后在新的窗体中查看完整图片。

技术分享

特别说明

欢迎转载。转载请注明出处【http://blog.csdn.net/derrantcm/article/details/47678205】

<script type="text/javascript"> $(function () { $(‘pre.prettyprint code‘).each(function () { var lines = $(this).text().split(‘\n‘).length; var $numbering = $(‘
    ‘).addClass(‘pre-numbering‘).hide(); $(this).addClass(‘has-numbering‘).parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($(‘
  • ‘).text(i)); }; $numbering.fadeIn(1700); }); }); </script>

【LeetCode-面试算法经典-Java实现】【129-Sum Root to Leaf Numbers(全部根到叶子结点组组成的数字相加)】