LeetCode 129. 求根到叶子节点数字之和 JAVA

待我称王封你为后i 2022-11-21 01:09 147阅读 0赞

给定一个二叉树，它的每个结点都存放一个 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.
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/sum-root-to-leaf-numbers
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：  
对于每一个结点而言，只有四种情况，分别是有左子树和右子树，只有左子树，只有右子树，或者为叶子结点，本题采用了递归解法，只需要考虑到这四种情况的各自返回值就可以了  
1、如果有左子树和右子树，那么到达该节点时的数字之和应该为左子树和右子树的的数字之和的和  
2、如果只有左子树，那么，到达该节点时的数字之和应该为左子树的数字之和而已  
3、如果只有右子树，同理可以得到，到达该节点时的数字之和应该为右子树的数字之和而已  
4、如果该节点为叶子结点，那么，就应该返回自身结点数字之和

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