“This is the 26th day of my participation in the November Gwen Challenge. See details of the event: The Last Gwen Challenge 2021”.

Find the sum of the numbers from the root to the leaf

You are given the root node of a binary tree. Each node in the tree contains a number between 0 and 9. Each path from the root node to the leaf node represents a number:

  • For example, the path 1 -> 2 -> 3 from the root node to the leaf node represents the number 123.

Computes the sum of all numbers generated from the root node to the leaf node.

Leaf nodes are nodes that have no children.

Examples can be found on the LeetCode website.

Source: LeetCode link: leetcode-cn.com/problems/su… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution 1: recursive method

Use recursion to solve this problem, recursion is as follows:

  • First, if the current node is null, it is an empty tree.
  • If the current node is not an NLL, add the value of the current node to path.
  • Add the current path value to result, and return result.
  • If the left node of the current node is not empty, the left node is recursively processed.
  • If the right node of the current node is not empty, the right node is recursively processed.

Finally, result is returned as the result value.

import com.kaesar.leetcode.TreeNode;

public class LeetCode_129 {
    // The final cumulative value
    private static int result = 0;

    public static int sumNumbers(TreeNode root) {
        sumNumbers(root, "");
        return result;
    }

    /** * recursion **@param root
     * @param path
     */
    private static void sumNumbers(TreeNode root, String path) {
        // If the current node is null, the tree is empty
        if (root == null) {
            return;
        }
        // Add the value of the current node to path
        path += root.val;
        // If the current node has no left or right children, it is a leaf node. Add the current path value to result and return result
        if (root.left == null && root.right == null) {
            result += Integer.valueOf(path);
            return;
        }
        if(root.left ! =null) {
            // If the left node of the current node is not empty, the left node is recursively processed
            sumNumbers(root.left, path);
        }
        if(root.right ! =null) {
            // If the right node of the current node is not empty, the right node is recursively processedsumNumbers(root.right, path); }}public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(9);
        root.right = new TreeNode(0);
        root.left.left = new TreeNode(5);
        root.left.right = new TreeNode(1);

        // Test case, expected output: 1026System.out.println(sumNumbers(root)); }}Copy the code

Life is like a gamble, it is impossible to win all, as long as the chips in their own hands, there will always be hope.