美文网首页
Sum Root to Leaf Numbers

Sum Root to Leaf Numbers

作者: 瞬铭 | 来源:发表于2019-12-03 10:44 被阅读0次

    https://leetcode.com/problems/sum-root-to-leaf-numbers/
    给定一个二叉树,求根节点到叶子节点的数字组成的所有十进制整数的和
    Example:
    Input: [1,2,3]
    1
    /
    2 3
    Output: 25
    Explanation:
    The root-to-leaf path 1->2 represents the number 12.
    The root-to-leaf path 1->3 represents the number 13.
    Therefore, sum = 12 + 13 = 25.
    Example 2:
    Input: [4,9,0,5,1]
    4
    /
    9 0
    /
    5 1
    Output: 1026
    Explanation:
    The root-to-leaf path 4->9->5 represents the number 495.
    The root-to-leaf path 4->9->1 represents the number 491.
    The root-to-leaf path 4->0 represents the number 40.
    Therefore, sum = 495 + 491 + 40 = 1026.

    题解

    类似path sum,用DFS求解

    • 维护一个sum变量,为当前已经求得的所有和
    • 遍历到某个节点时候,用sum * 10 加上当前节点的val
    • 如果到叶子节点,直接返回结果
    • 非叶子节点,对其子节点继续DFS递归
      /**
         * @param root
         * @return
         */
          public int sumNumbersDFS(TreeNode root, int sum) {
            if (root == null) {
                return 0;
            }
    
            //父节点的和值
            //父节点的值扩大10倍后加上该节点的val
            sum = sum * 10 + root.val;
    
            //此节点是叶子节点,直接返回,不进行处理
            if (root.left == null && root.right == null) {
                return sum;
            }
    
            int leftSum = sumNumbersDFS(root.left, sum);
    
            int rightSum = sumNumbersDFS(root.right, sum);
    
            return leftSum + rightSum;
        }
    

    相关文章

      网友评论

          本文标题:Sum Root to Leaf Numbers

          本文链接:https://www.haomeiwen.com/subject/emqcgctx.html