[LeetCode] 1026. Maximum Difference Between Node and Ancestor

https://leetcode.com/problems/maximum-difference-between-node-and-ancestor/description/

Maximum Difference Between Node and Ancestor - LeetCode

leetcode - Maximum Difference Between Node and Ancestor

문제 유형 : dfs/bfs, 이진트리

문제 난이도 : 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.

 

이진 트리의 루트가 주어진다. 조상 노드들과 비교해서 가장 차이가 큰 값을 구하시오.

조상 노드는 노드의 부모노드이거나, 부모노드의 조상노드인 경우, 조상노드라고 할 수 있습니다.

 

 

풀이

dfs로 순회하면서, 매번 최대 차이를 갱신하면 된다.

최대 차이 값을 구할 때는, 이전까지 탐색해오면서 가장 큰 값과 가장 작은 값에서만 구하면 된다. 둘과의 차에서 더 큰 값이 더 큰 차이다.

이 값을 매번 갱신해준 다음, 가장 큰 값과 가장 작은 값을 갱신하여 재귀적으로 계속 탐색하고 나면, 최대 차이값이 구해진다.

 

코드

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int maxGap = 0;
    void traverse(TreeNode* root, int currMax, int currMin) {
        maxGap = max(maxGap, max(abs(currMax - root -> val), abs(currMin - root -> val)));

        currMax = max(currMax, root -> val);
        currMin = min(currMin, root -> val);

        if(root -> left) {
            traverse(root -> left, currMax, currMin);
        }
        if(root -> right) {
            traverse(root -> right, currMax, currMin);
        }
    } 

    int maxAncestorDiff(TreeNode* root) {
        if(root == nullptr) return 0;
        traverse(root, root -> val, root -> val);
        return maxGap;
    }
};