113. Path Sum II

💡 풀이

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {number[][]}
 */
var pathSum = function (root, targetSum) {
  if (!root) return [];
  let result = [];
  const recurPathSum = (node, target, path) => {
    if (!node.left && !node.right && target === node.val) {
      // console.log('path: ', path);
      result.push(path);
    }

    if (node.left)
      recurPathSum(node.left, target - node.val, [...path, node.left.val]);
    if (node.right)
      recurPathSum(node.right, target - node.val, [...path, node.right.val]);
  };
  recurPathSum(root, targetSum, [root.val]);
  return result;
};
let root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1];
let targetSum = 22;

pathSum(root, targetSum);

📝 정리

• 트리 탐색 문제의 기본이 되는 문제라고 한다. 문제의 요구사항은 아래 그림처럼 탐색한 노드의 value값의 합이 targetSum과 일치하는 배열을 담아서 return하라는 문제다.
  

• 이 문제는 먼저 트리 탐색에 대한 이해가 있어야 한다. 루트 노드부터 탐색을 시작하는 것이 기본 조건이다. 코드를 보자.

if (!root) return [];
let result = [];

• 이 코드는 root 배열에 아무 것도 없을 경우 빈 배열을 return한다. 예외처리다.

• 결과값을 담을 result 배열을 생성한다.

// 맨 아래 라인
recurPathSum(root, targetSum, [root.val]);

• 나는 재귀 탐색으로 문제를 풀었다. 따라서 처음 함수 호출을 할 때, 파라미터로 들어갈 값을 지정해준다. root, targetSum, [root.val]

  여기서 root.val은 노드의 value 값이다. root 배열의 요소 값이란 뜻이다.(= 5, 4, 8...)

const recurPathSum = (node, target, path) => {
    if (!node.left && !node.right && target === node.val) {
      // console.log('path: ', path);
      result.push(path);
    }

    if (node.left)
      recurPathSum(node.left, target - node.val, [...path, node.left.val]);
    if (node.right)
      recurPathSum(node.right, target - node.val, [...path, node.right.val]);
  };

• 이제 재귀 함수 부분이다. 그 중 아래 코드부터 보자.

  if (node.left)
      recurPathSum(node.left, target - node.val, [...path, node.left.val]);
  if (node.right)
      recurPathSum(node.right, target - node.val, [...path, node.right.val]);

• 재귀적으로 탐색하는 부분이다. 첫 번째 조건문 if(node.left)는 노드의 왼쪽에 값이 있을 때 다시 recurPathSum 함수를 호출해준다.

• [...path, node.left.val] 마지막 인자로 들어가는 이 파라미터는, 지금까지의 path, 즉 답이 될 값을 저장하는 배열이다. ...path와 같이 스프레드 연산자를 통해 계속 쌓아준다.

• 두번째 조건문은 노드의 오른쪽에 값이 있을 때 recurPathSUm 함수를 호출한다. 작동은 같다.

  if (!node.left && !node.right && target === node.val) {
      // console.log('path: ', path);
      result.push(path);
    }

• 위쪽 코드인 종료 조건을 보자. 더 이상 아래로 탐색해 나갈 노드가 없고, target이 node.val값과 같다면 그게 바로 답이 될 수 있는 조건이기 때문에 result 배열에 path를 넣어준다.

• 이렇게 재귀 함수가 마지막에 종료될 때 result 배열에 정답이 될 값이 있을 것이다.

수정, 지적을 환영합니다!

문제 링크

https://leetcode.com/problems/path-sum-ii/

LeetCode GitHub

https://github.com/tTab1204/LeetCode