112. Path Sum

public class Solution {
    public bool HasPathSum(TreeNode root, int sum) {
        if (root == null)
            return false;
        Stack<TreeNode> nodeStack = new Stack<TreeNode>();
        Stack<int> sumStack = new Stack<int>();
        nodeStack.Push(root);
        sumStack.Push(sum - root.val);
        while (nodeStack.Count > 0) {
            TreeNode node = nodeStack.Pop();
            int currSum = sumStack.Pop();
            if (node.left == null && node.right == null && currSum == 0)
                return true;
            if (node.left != null) {
                nodeStack.Push(node.left);
                sumStack.Push(currSum - node.left.val);
            }
            if (node.right != null) {
                nodeStack.Push(node.right);
                sumStack.Push(currSum - node.right.val);
            }
        }
        return false;
    }
}

#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 bool HasPathSum(TreeNode root, int sum) {
        if (root == null)
            return false;
        stack<TreeNode> nodeStack = new stack<TreeNode>();
        stack<int> sumStack = new stack<int>();
        nodeStack.push(root);
        sumStack.push(sum - root.val);
        while (nodeStack.size() > 0) {
            TreeNode node = nodeStack.pop();
            int currSum = sumStack.pop();
            if (node.left == null && node.right == null && currSum == 0)
                return true;
            if (node.left != null) {
                nodeStack.push(node.left);
                sumStack.push(currSum - node.left.val);
            }
            if (node.right != null) {
                nodeStack.push(node.right);
                sumStack.push(currSum - node.right.val);
            }
        }
        return false;
    }
}

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) return false;

        LinkedList<TreeNode> node_stack = new LinkedList();
        LinkedList<Integer> sum_stack = new LinkedList();
        node_stack.add(root);
        sum_stack.add(sum - root.val);

        TreeNode node;
        int curr_sum;
        while (!node_stack.isEmpty()) {
            node = node_stack.pollLast();
            curr_sum = sum_stack.pollLast();
            if (
                (node.right == null) && (node.left == null) && (curr_sum == 0)
            ) return true;

            if (node.right != null) {
                node_stack.add(node.right);
                sum_stack.add(curr_sum - node.right.val);
            }
            if (node.left != null) {
                node_stack.add(node.left);
                sum_stack.add(curr_sum - node.left.val);
            }
        }
        return false;
    }
}

var hasPathSum = function (root, sum) {
    if (!root) return false;
    let nodeStack = [];
    let sumStack = [];
    nodeStack.push(root);
    sumStack.push(sum - root.val);
    while (nodeStack.length > 0) {
        let currentNode = nodeStack.pop();
        let currSum = sumStack.pop();
        if (!currentNode.left && !currentNode.right && currSum === 0)
            return true;
        if (currentNode.right) {
            nodeStack.push(currentNode.right);
            sumStack.push(currSum - currentNode.right.val);
        }
        if (currentNode.left) {
            nodeStack.push(currentNode.left);
            sumStack.push(currSum - currentNode.left.val);
        }
    }
    return false;
};

class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if not root:
            return False

        de = [
            (root, sum - root.val),
        ]
        while de:
            node, curr_sum = de.pop()
            if not node.left and not node.right and curr_sum == 0:
                return True
            if node.right:
                de.append((node.right, curr_sum - node.right.val))
            if node.left:
                de.append((node.left, curr_sum - node.left.val))
        return False

func hasPathSum(root *TreeNode, sum int) bool {
    if root == nil {
        return false
    }
    nodeStack := []*TreeNode{}
    sumStack := []int{}
    nodeStack = append(nodeStack, root)
    sumStack = append(sumStack, sum-root.Val)
    for len(nodeStack) > 0 {
        lastIdx := len(nodeStack) - 1
        currentNode := nodeStack[lastIdx]
        nodeStack = nodeStack[:lastIdx]
        currSum := sumStack[lastIdx]
        sumStack = sumStack[:lastIdx]
        if currentNode.Left == nil && currentNode.Right == nil && currSum == 0 {
            return true
        }
        if currentNode.Right != nil {
            nodeStack = append(nodeStack, currentNode.Right)
            sumStack = append(sumStack, currSum-currentNode.Right.Val)
        }
        if currentNode.Left != nil {
            nodeStack = append(nodeStack, currentNode.Left)
            sumStack = append(sumStack, currSum-currentNode.Left.Val)
        }
    }
    return false
}

Algorithm

1️⃣

Инициализация стека: Начать с помещения в стек корневого узла и соответствующей оставшейся суммы, равной sum - root.val.

2️⃣

Обработка узлов: Извлечь текущий узел из стека и вернуть True, если оставшаяся сумма равна 0 и узел является листом.

3️⃣

Добавление дочерних узлов в стек: Если оставшаяся сумма не равна нулю или узел не является листом, добавить в стек дочерние узлы с соответствующими оставшимися суммами.

😎