문제

Find the path with the maximum sum in a given binary tree. Write a function that returns the maximum sum.

A path can be defined as a sequence of nodes between any two nodes and doesn’t necessarily pass through the root. The path must contain at least one node.

input & output

Example 1

input tree:

    1
   / \
  2   3
 /   / \
4   5   6

output: 16

Explanation: The path with maximum sum is: [4, 2, 1, 3, 6].

Example 2

input tree:

        1
      /    \
   2         3
 /  \      /   \
1    3    5     6
        /  \     \
       7   8      9

output: 31

Explanation: Thr Path with maximum sum is: [8, 5, 3, 6, 9].

---

Approach #1

tree의 왼쪽, 오른쪽을 dfs로 들어가며 확인하는데,

dfs에서는 해당 노드에서의 합과 경로를 리턴해준다.

dfs.....로직.
curSum = left+right+curVal.
curSum이 maxSum보다 크면 maxSum 갱신해줌.
이때 경로는 left 경로 -현재 값 - right 경로여야함.
** right 경로는 역방향으로 넣어주어야 전체 path가 이어짐.

다음 dfs 탐색을 위해 left->root, right->root 경로중 더 큰 경로를 리턴해준다. 

Solution #1

//tree 생성
function Node(val, left, right){
  this.val = (val === undefined ? 0 : val);
  this.left = (left === undefined ? null : left);
  this.right = (right === undefined ? null : right);
}

//input tree1
const tree1 = new Node(
  1,
  new Node(2,new Node(4)), 
  new Node(3, new Node(5), new Node(6))
);

//input tree2
const tree2 = new Node(
  1,
  new Node(2, new Node(1), new Node(3)),
  new Node(3, 
    new Node(5, new Node(7), new Node(8)),
    new Node(6, new Node(9))
  )
);

function findMaxPath(tree) {
  // edge case
  if(!tree) return [];
  
  let maxSum = Number.MIN_VALUE;
  let path = [];

  const dfs = (node) => {
    let leftSum = 0;
    let rightSum = 0;
    let leftPath = [];
    let rightPath = [];

    //left,right가 존재하면 dfs 들어감
    if(node.left) [leftSum, leftPath] = dfs(node.left);
    if(node.right) [rightSum, rightPath] = dfs(node.right);

    //left->root->right Path
    const curSum = leftSum + rightSum + node.val;
    console.log(maxSum, curSum)
    if(maxSum < curSum) {
      maxSum = curSum;
      const reversed = [...rightPath].reverse();
      path = [...leftPath, node.val, ...reversed];
    }

    // left -> root || right -> root 중 더 큰 값을 리턴함
    return leftSum >= rightSum ? [leftSum+node.val, [...leftPath, node.val]] : [rightSum+node.val, [...rightPath, node.val]];

  }

  dfs(tree);
  return path;
}

N: # of nodes
H: height of tree

Time Complexity

O(N)

tree의 모든 노드를 확인하기 때문에 O(N)

Space Complexity

O(H+2H)=>O(H)

dfs가 한번 실행될때 H만큼 콜스택이 쌓이면서 dfs가 실행되고, Path가 가장 길때가 left leaf node -> root -> right leaf node 이기 때문에 2H가 된다.

---