129. Sum Root to Leaf Numbers

leetcode medium

#bit-manipulation#csharp#graph#leetcode#medium#stack#tree#two-pointers

Task

Вам дан корень бинарного дерева, содержащего только цифры от 0 до 9.

Каждый путь от корня до листа в дереве представляет собой число.

Например, путь от корня до листа 1 -> 2 -> 3 представляет число 123.

Верните общую сумму всех чисел от корня до листа. Тестовые случаи созданы таким образом, что ответ поместится в 32-битное целое число.

Листовой узел — это узел без детей.

Пример:

Input: root = [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.

C# solution

matched/original

public class Solution {
    public int SumNumbers(TreeNode root) {
        int rootToLeaf = 0, currNumber = 0;
        int steps;
        TreeNode predecessor;
        while (root != null) {
            if (root.left != null) {
                predecessor = root.left;
                steps = 1;
                while (predecessor.right != null && predecessor.right != root) {
                    predecessor = predecessor.right;
                    ++steps;
                }
                if (predecessor.right == null) {
                    currNumber = currNumber * 10 + root.val;
                    predecessor.right = root;
                    root = root.left;
                } else {
                    if (predecessor.left == null) {
                        rootToLeaf += currNumber;
                    }
                    for (int i = 0; i < steps; ++i) {
                        currNumber /= 10;
                    }
                    predecessor.right = null;
                    root = root.right;
                }
            } else {
                currNumber = currNumber * 10 + root.val;
                if (root.right == null) {
                    rootToLeaf += currNumber;
                }
                root = root.right;
            }
        }
        return rootToLeaf;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int SumNumbers(TreeNode root) {
        int rootToLeaf = 0, currNumber = 0;
        int steps;
        TreeNode predecessor;
        while (root != null) {
            if (root.left != null) {
                predecessor = root.left;
                steps = 1;
                while (predecessor.right != null && predecessor.right != root) {
                    predecessor = predecessor.right;
                    ++steps;
                }
                if (predecessor.right == null) {
                    currNumber = currNumber * 10 + root.val;
                    predecessor.right = root;
                    root = root.left;
                } else {
                    if (predecessor.left == null) {
                        rootToLeaf += currNumber;
                    }
                    for (int i = 0; i < steps; ++i) {
                        currNumber /= 10;
                    }
                    predecessor.right = null;
                    root = root.right;
                }
            } else {
                currNumber = currNumber * 10 + root.val;
                if (root.right == null) {
                    rootToLeaf += currNumber;
                }
                root = root.right;
            }
        }
        return rootToLeaf;
    }
}

Java solution

matched/original

class Solution {
    public int sumNumbers(TreeNode root) {
        int rootToLeaf = 0, currNumber = 0;
        int steps;
        TreeNode predecessor;

        while (root != null) {
            if (root.left != null) {
                predecessor = root.left;
                steps = 1;
                while (predecessor.right != null && predecessor.right != root) {
                    predecessor = predecessor.right;
                    ++steps;
                }

                if (predecessor.right == null) {
                    currNumber = currNumber * 10 + root.val;
                    predecessor.right = root;
                    root = root.left;
                } else {
                    if (predecessor.left == null) {
                        rootToLeaf += currNumber;
                    }
                    for (int i = 0; i < steps; ++i) {
                        currNumber /= 10;
                    }
                    predecessor.right = null;
                    root = root.right;
                }
            } else {
                currNumber = currNumber * 10 + root.val;
                if (root.right == null) {
                    rootToLeaf += currNumber;
                }
                root = root.right;
            }
        }
        return rootToLeaf;
    }
}

JavaScript solution

matched/original

function sumNumbers(root, partialSum = 0) {
    if (!root) {
        return 0;
    }
    partialSum = partialSum * 10 + root.val;
    if (!root.left && !root.right) {
        return partialSum;
    }
    return (
        sumNumbers(root.left, partialSum) + sumNumbers(root.right, partialSum)
    );
}

Python solution

matched/original

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        root_to_leaf = curr_number = 0

        while root:
            if root.left:
                predecessor = root.left
                steps = 1
                while predecessor.right and predecessor.right is not root:
                    predecessor = predecessor.right
                    steps += 1

                if predecessor.right is None:
                    curr_number = curr_number * 10 + root.val
                    predecessor.right = root
                    root = root.left
                else:
                    if predecessor.left is None:
                        root_to_leaf += curr_number
                    for _ in range(steps):
                        curr_number //= 10
                    predecessor.right = None
                    root = root.right
            else:
                curr_number = curr_number * 10 + root.val
                if root.right is None:
                    root_to_leaf += curr_number
                root = root.right

        return root_to_leaf

Go solution

matched/original

func sumNumbers(root *TreeNode) int {
    root_to_leaf, curr_number, steps := 0, 0, 0
    var predecessor *TreeNode
    for root != nil {
        if root.Left != nil {
            predecessor = root.Left
            steps = 1
            for predecessor.Right != nil && predecessor.Right != root {
                predecessor = predecessor.Right
                steps++
            }
            if predecessor.Right == nil {
                curr_number = curr_number*10 + root.Val
                predecessor.Right = root
                root = root.Left
            } else {
                if predecessor.Left == nil {
                    root_to_leaf += curr_number
                }
                for i := 0; i < steps; i++ {
                    curr_number /= 10
                }
                predecessor.Right = nil
                root = root.Right
            }
        } else {
            curr_number = curr_number*10 + root.Val
            if root.Right == nil {
                root_to_leaf += curr_number
            }
            root = root.Right
        }
    }
    return root_to_leaf
}

Explanation

Algorithm

1️⃣

Инициализация:

Создайте переменные для хранения суммы чисел (rootToLeaf) и текущего числа (currNumber), а также стек для обхода дерева, начиная с корневого узла.

2️⃣

Обход дерева:

Используйте стек для глубинного обхода дерева (DFS), обновляя currNumber путём умножения на 10 и добавления значения узла. Для каждого листа добавляйте currNumber к rootToLeaf.

3️⃣

Возвращение результата:

По завершении обхода всех узлов возвращайте rootToLeaf, содержащую сумму всех чисел от корня до листьев дерева.

😎