129. 求根到叶子节点数字之和（树）

一时失言乱红尘 2022-11-21 04:10 165阅读 0赞

# 1.题目描述 #

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

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

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

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

示例 1:

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

# 2.java代码 #

package com.tree.medium.LeetCode129;
    
    import java.util.LinkedList;
    import java.util.Queue;
    
    /**
     * @author GMT
     * @version 1.0
     * @create 2020-10-2922:00
     */
    // 结构体构造tree
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
    
        TreeNode(int x) {
            this.val = x;
        }
    
        //添加结点
        public TreeNode addNode(TreeNode parentNode, int data, boolean isLeft) {
            //父节点为空，无法添加子节点
            if (parentNode == null)
                throw new RuntimeException("父节点为空，无法添加子节点");
            if (isLeft && parentNode.left != null)
                throw new RuntimeException("左子节点已经存在，添加失败");
            if (!isLeft && parentNode.right != null)
                throw new RuntimeException("右子节点已经存在，添加失败");
            TreeNode newNode = new TreeNode(data);
            if (isLeft) {
                parentNode.left = newNode;
            } else {
                parentNode.right = newNode;
            }
            return newNode;
        }
    }
    
    public class Solution {
        /**
         * 方法一：
         * 使用深度优先遍历方法
         * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
         * 内存消耗：36.4 MB, 在所有 Java 提交中击败了76.76%的用户
         * 时间复杂度：O(n)，其中 n 是二叉树的节点个数。对每个节点访问一次。
         * 空间复杂度：O(n)，其中 n 是二叉树的节点个数。
         * 空间复杂度主要取决于递归调用的栈空间，递归栈的深度等于二叉树的高度，最坏情况下，二叉树的高度等于节点个数，
         *
         * 首先定义一个sum为0，遍历从根结点开始计算dfs(root,sum)
         * 当根节点为空返回，否则，将之前和*10加上现在节点的值，赋值给sum变量
         * 当左右为空时候，返回sum，否则返回dfs(left,sum)+dfs(right,sum)
         */
        public int sumNumbers1(TreeNode root) {
            return dfs(root, 0);
        }
    
        private int dfs(TreeNode node, int preSum) {
            if (node == null) {
                return 0;
            }
            int sum = preSum * 10 + node.val;
            if (node.left == null && node.right == null) {
                return sum;
            } else {
                return dfs(node.left, sum) + dfs(node.right, sum);
            }
        }
    
        /**
         * 方法二：
         * 使用广度优先遍历
         * 执行用时：1 ms, 在所有 Java 提交中击败了31.18%的用户
         * 内存消耗：36.5 MB, 在所有 Java 提交中击败了70.85%的用户
         *
         * 使用java中队列 linkedlist的父类是queue队列
         * Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
         * 用到了里面的offer和poll方法
         */
        public int sumNumbers2(TreeNode root) {
            if (root == null) return 0;
            int sum = 0;
            Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
            Queue<Integer> numQueue = new LinkedList<Integer>();
            nodeQueue.offer(root);
            numQueue.offer(root.val);
            while (!nodeQueue.isEmpty()) {
                TreeNode node = nodeQueue.poll();
                int num = numQueue.poll();
                TreeNode left = node.left;
                TreeNode right = node.right;
                if (left == null && right == null) sum += num;
                else {
                    if (left != null) {
                        nodeQueue.offer(left);
                        numQueue.offer(num * 10 + left.val);
                    }
                    if (right != null) {
                        nodeQueue.offer(right);
                        numQueue.offer(num * 10 + right.val);
                    }
                }
            }
            return sum;
        }
    
    
        public static void main(String[] args) {
            TreeNode root = new TreeNode(1);
            root.addNode(root, 1, true);//11
            root.addNode(root, 2, false);//12
            Solution solution = new Solution();
            int ans1 = solution.sumNumbers1(root);
            System.out.println(ans1);
            int ans2 = solution.sumNumbers2(root);
            System.out.println(ans2);
        }
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1eWViaXViaXU_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1eWViaXViaXU_size_16_color_FFFFFF_t_70]: /images/20221120/3201d060ee144c909892a42e195d683d.png