[leetCode/JS] 1026. Maximum Difference Between Node and Ancestor

난이도 [ 🤔 ] Medium

 

문제 설명

Given the root of a binary tree, find the maximum value v for which there exist different nodes a and b where v = |a.val - b.val| and a is an ancestor of b.

A node a is an ancestor of b if either: any child of a is equal to b or any child of a is an ancestor of b.

이진트리의 상위, 하위 노드의 a-b 의 최대값을 찾는 문제다.

 

입출력 예

Example 1:

Input: root = [8,3,10,1,6,null,14,null,null,4,7,13]
Output: 7
Explanation: We have various ancestor-node differences, some of which are given below :
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
Among all possible differences, the maximum value of 7 is obtained by |8 - 1| = 7.

 

Example 2:

Input: root = [1,null,2,null,0,3]
Output: 3

 

 

Constraints

• The number of nodes in the tree is in the range [2, 5000].
• 0 <= Node.val <= 105

 

---

 

 

내 솔루션

• 2진트리 DFS로 서치한다.
• left, right로 나눠진 트리를 서치하면서 max, min을 구한다.
• 마지막 노드일때 max - min 해서 left와 right 트리의 큰 값을 리턴한다.

var maxAncestorDiff = function(root) {
  const dfs = (node, max, min) => {
    if(!node) return Math.abs(max - min);

    max = Math.max(max, node.val)
    min = Math.min(min, node.val)

    let leftMax = dfs(node.left, max, min);
    let rightMax = dfs(node.right, max, min);
    return Math.max(leftMax, rightMax)
  }
  return dfs(root, 0, Infinity);
};

 

감상평

• return 값을 이용하여 dfs로 풀면 쉽다. 
• 요즘 이진트리 서치나 dfs 위주로 나와서 덕분에 DFS에 자신감이 많이 생겼다.