[LeetCode] 1026. Maximum Difference Between Node and Ancestor

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

Maximum Difference Between Node and Ancestor - LeetCode

Maximum Difference Between Node and Ancestor - Medium

 

이진트리가 주어질때, 상위 노드와 하위 노드의 차의 최대값을 구하는 문제다.

 

모든 노드를 dfs로 방문하며 그 때 방문했던 노드들 중 최대값과 최소값을 구해준다.

leaf 노드에 도달할 경우, 최대값과 최소값의 차를 return 해주고,

leaf가 아닌 노드일 경우엔 왼쪽 자식과 오른쪽 자식에 대해 다시 수행해준값 중 최대값을 골라주자.

 

전체 풀이 코드

class Solution {
public:
    int maxAncestorDiff(TreeNode* root) {return run(root, root->val, root->val);}
    int run(TreeNode* node, int M, int m) {
        if (!node) return M-m;
        M = max(node->val, M);
        m = min(node->val, m);
        return max(run(node->left, M, m),run(node->right, M, m));
    }
};