Maximum Difference Between Node and Ancestor(Tree,Depth-First Search,Binary Tree)

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

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.

 

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

또 Tree문제이긴 한데, 이건 좀 난이도가 있을듯하다. Medium으로 책정되어 있길래;;

그래도 뭐.. 쫄 필요는 없다. 그래봐야 일개 코딩문제임요!

코나우딩요!

 

아 어렵다. 뇌 꼬인다

Recursive하게 풀 수 있을 거 같긴한데,, 가다가 잡히지 않는다.

 

좀만 더 고민해보자 ㅠㅠ

 

1. Python

아.. 결국 답지를 보았다.

 

짜증이나고 너무 찝찝하다..

생각해내기가 너무 어려웠던 Recursive 문제 ㅠㅠ

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
        def dfs(node,curr_max,curr_min):
            if not node : return 0

            curr_max = max(curr_max,node.val)
            curr_min = min(curr_min,node.val)

            if not node.left and not node.right :
                return curr_max - curr_min

            left = dfs(node.left,curr_max,curr_min)
            right = dfs(node.right,curr_max,curr_min)

            return max(left,right)

        return dfs(root,root.val,root.val)

 

현타가 온다. Medium만 되어도 이렇게 힘들구나..

 

 

2. C

C로도 비슷하게 풀어보고, C++의 경우 Stack + while문으로 풀어보겠다. 에효..

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int max(int a, int b){
    return a > b ? a : b;
}
int min(int a, int b){
    return a > b? b : a;
}

int helper(struct TreeNode* node, int maxval, int minval){
    if(!node) return maxval - minval;
    maxval = max(maxval,node->val);
    minval = min(minval,node->val);
    int left = helper(node->left,maxval,minval);
    int right = helper(node->right,maxval,minval);
    return max(left,right);
}

int maxAncestorDiff(struct TreeNode* root) {
    return helper(root,root->val,root->val);
}

 

 

3. C++

이번엔 Stack으로 함 풀어보자 마!

 

답지좀 봤다.. 요지는 Tuple이라는 Container를 사용할 수 있냐는 것이었다.

Tree Node와 Min/Max int value를 모두 넣는 container가 필요했는데 생각해보니 Vector의 경우 Python의 list처럼 data type을 짬뽕시켜서 넣을 수가 없는 것이었다.

 

덕분에 처음보는 Tuple이라는 녀석을 사용할 수 있었다.

 

/**
 * 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) {}
 * };
 */
class Solution {
public:
    int maxAncestorDiff(TreeNode* root) {
        int ans = 0;
        stack<tuple<TreeNode*,int,int>> s;
        s.push({root,root->val,root->val});

        while(!s.empty()){
            auto [curr, maxval, minval] = s.top();
            s.pop();

            maxval = max(curr->val,maxval);
            minval = min(curr->val,minval);

            ans = max(ans,maxval-minval);

            if(curr->left) s.push({curr->left,maxval,minval});
            if(curr->right) s.push({curr->right,maxval,minval});
        }
        return ans;
    }
};

 

요기까지...ㅎ