dev/democards/problems/problems/437.path-sum-iii.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "source": [
    "You are given a binary tree in which each node contains an integer value.\n",
    "\n",
    "Find the number of paths that sum to a given value.\n",
    "\n",
    "The path does not need to start or end at the root or a leaf, but it must go\n",
    "downwards (traveling only from parent nodes to child nodes).\n",
    "\n",
    "The tree has no more than 1,000 nodes and the values are in the range\n",
    "-1,000,000 to 1,000,000.\n",
    "\n",
    "**Example:**\n",
    "\n",
    "\n",
    "\n",
    "    root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8\n",
    "\n",
    "          10\n",
    "         /  \\\n",
    "        **5**   **-3**\n",
    "       **/** **\\**    **\\**\n",
    "      **3**   **2**   **11**\n",
    "     / \\   **\\**\n",
    "    3  -2   **1**\n",
    "\n",
    "    Return 3. The paths that sum to 8 are:\n",
    "\n",
    "    1.  5 -> 3\n",
    "    2.  5 -> 2 -> 1\n",
    "    3. -3 -> 11"
   ],
   "metadata": {}
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "tree_path_sum (generic function with 2 methods)"
     },
     "metadata": {},
     "execution_count": 1
    }
   ],
   "cell_type": "code",
   "source": [
    "# @lc code=start\n",
    "using LeetCode\n",
    "\n",
    "function tree_path_sum(root::TreeNode{Int}, sm::Int)::Int\n",
    "    res = 0\n",
    "    tsum(::Nothing, sm::Int) = nothing\n",
    "    function tsum(root::TreeNode{Int}, sm::Int)::Nothing\n",
    "        sm -= root.val\n",
    "        sm == 0 && (res += 1)\n",
    "        tsum(root.left, sm)\n",
    "        tsum(root.right, sm)\n",
    "    end\n",
    "    tsum(root, sm)\n",
    "    res += tree_path_sum(root.left, sm)\n",
    "    res += tree_path_sum(root.right, sm)\n",
    "end\n",
    "\n",
    "tree_path_sum(root::Nothing, sum::Int) = 0\n",
    "# @lc code=end"
   ],
   "metadata": {},
   "execution_count": 1
  },
  {
   "cell_type": "markdown",
   "source": [
    "---\n",
    "\n",
    "*This notebook was generated using [Literate.jl](https://github.com/fredrikekre/Literate.jl).*"
   ],
   "metadata": {}
  }
 ],
 "nbformat_minor": 3,
 "metadata": {
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.10.1"
  },
  "kernelspec": {
   "name": "julia-1.10",
   "display_name": "Julia 1.10.1",
   "language": "julia"
  }
 },
 "nbformat": 4
}