Сумма путей II двоичного дерева

Проблема

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
Note: A leaf is a node with no children.
Example:
Given the below binary tree and sum = 22,
5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1

Возвращение:

[
   [5,4,11,2],
   [5,8,4,5]
]

Решение:

*Давайте создадим массив, в котором будут храниться все возможности дерева, где сумма значений корневого узла и конечного узла равна сумме.
* мы вызываем функцию, где параметром являются узел, массив, текущая сумма
* при первом вызове текущий узел является корневым, массив представляет собой пустой массив (чтобы поместить все значения узлов от корня к листу) и текущая сумма = 0.
* текущая сумма будет суммой от корня => листа.
* мы проверяем, является ли сумма листьев (то есть сумма от корня до листьев) ‹= суммой для сравнения.
*
* Если это так, то мы проверяем, есть ли левый или правый узел. если есть, то мы рекурсивно вызываем функцию с узлом в качестве текущего node.left и более поздним текущим node.right .
* мы возвращаемся из функции, когда левый и правый узлы текущего узла равны нулю.
* когда мы возвращаемся из функции, мы извлекаем значение последнего переданного значения левого или правого узла, чтобы остальная часть пройденного узла сохраняется.
*
* Если сумма равна leafsum и если нет левого и правого узлов, то мы создаем отдельную копию текущего пройденного массива и вставляем в окончательный возвращаемый массив.
*
* После обхода всех узлов мы возвращаем окончательный возвращаемый массив, который содержит массив возможных комбинаций узлов, сумма которых от корня до листа равна сумме.

Псевдокод

step 1: initial an empty return array
step 2: call the function where the parameters are root node, empty array , current sum = 0 .
step 3: inside the function. 
     a. check if the node exist .
     b. True: 
         i: Add the current node value to the current sum 
         ii: check if node.left or node.right exist
         iii: True
            * Traverse to Left/right most node First 
            * Repeat step a.
         iv: False
            * check the sum == current sum . 
               True: push the current array to return array
          v. Pop the last push value from the array.
          vi: repeat ii until all the nodes values are read.
step 4: Return the return array.

Код:

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {number[][]}
 */
var pathSum = function(root, sum) {
     
    var finalArray=[];
    function FindRootToLeaf(node,arr,leafSum){
        if(node){
            leafSum+=node.val;
            arr.push(node.val);
            // console.log(arr, leafSum); 
// //             check if the current leaf sum is less than or equal to sum . if its greater then we neednot traverse futher down the tree.
//             if(leafSum <= sum){
              if(node.left || node.right){
                if(node.left){
                FindRootToLeaf(node.left,arr,leafSum);
                arr.pop();
                } if(node.right){
                FindRootToLeaf(node.right,arr,leafSum);
                arr.pop();
                } 
            }else{
              if(sum == leafSum){
                // console.log(arr);
//        creating a new temp array,helps to avoid the reference array problem.
//                   if we dont create a new copy, every time when the arr changes, the value in final array also changes as we are pushing the reference array of arr.
                  var temp = arr.map(elem => elem);
                finalArray.push(temp);  
                }  
            }   
        }  
    }
    FindRootToLeaf(root,[],0);
    // console.log('finalArray '+ finalArray);
    return finalArray;
};

Сумма путей II двоичного дерева

Похожие вопросы