LeetCode 솔루션

[interview] 1026. Maximum Difference Between Node and Ancestor

mingki 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.06.09 22:41

7,716 조회
3 댓글
0 추천
0 비추천
목록 게시글 쓰기

1026. Maximum Difference Between Node and Ancestor

Medium

239464Add to ListShare

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

#Amazon, #Facebook, #Google, #Tree, #Depth-First Search(DFS), #Binary Tree

링크

https://leetcode.com/problems/maximum-difference-between-node-and-ancestor/ 1202 회 연결

익명
작성일 2022.06.09 22:42

C++
Runtime: 14 ms, faster than 19.81% of C++ online submissions for Maximum Difference Between Node and Ancestor.
Memory Usage: 9.8 MB, less than 58.79% of C++ online submissions for Maximum Difference Between Node and Ancestor.

class Solution {
public:
    int maxAncestorDiff(TreeNode* root, int minVal = 1e5 + 1, int maxVal = -1e5 - 1) {
        if (!root) return 0;
        
        int tmp = minVal > 1e5 ? 0 :
                  max(abs(minVal - root->val), abs(maxVal - root->val));
        
        minVal = min(minVal, root->val);
        maxVal = max(maxVal, root->val);
        
        int child = max(maxAncestorDiff(root->left, minVal, maxVal), maxAncestorDiff(root->right, minVal, maxVal));
        
        return max(tmp, child);
    }
};

익명
작성일 2022.06.10 15:02

Runtime: 73 ms, faster than 23.29% of Python3 online submissions for Maximum Difference Between Node and Ancestor.
Memory Usage: 20.3 MB, less than 19.92% of Python3 online submissions for Maximum Difference Between Node and Ancestor.

# 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, minval, maxval):
            if not node: return 0
            
            
            temp = max(abs(node.val - minval), abs(node.val-maxval)) if minval < 10e5 else 0
            minval = min(minval, node.val)
            maxval = max(maxval, node.val)
            
            temp2 = max(dfs(node.left, minval, maxval),dfs(node.right,minval,maxval))
            
            return max(temp, temp2)

        return dfs(root, 10e5, -10e5)

[code=Python 3]# 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, minval, maxval):
            if not node: return 0
            
            
            temp = max(abs(node.val - minval), abs(node.val-maxval)) if minval < 10e5 else 0
            minval = min(minval, node.val)
            maxval = max(maxval, node.val)
            
            temp2 = max(dfs(node.left, minval, maxval),dfs(node.right,minval,maxval))
            
            return max(temp, temp2)

return dfs(root, 10e5, -10e5)[/code]

익명
작성일 2022.06.11 17:09

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int result = 0;
    private void dfs(TreeNode node, int currMax, int currMin){
        if(node == null){
            return;
        }
        int currMaxDiff = Math.max(Math.abs(currMax - node.val), Math.abs(currMin - node.val));
        result = Math.max(result, currMaxDiff);
        currMax = Math.max(currMax, node.val);
        currMin = Math.min(currMin, node.val);
        dfs(node.left, currMax, currMin);
        dfs(node.right, currMax, currMin);    
        return;
    }
    
    public int maxAncestorDiff(TreeNode root) {
        if(root == null){
            return 0;
        }
        dfs(root, root.val, root.val);
        return result;
    }
    
    
}

[code=java]/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int result = 0;
    private void dfs(TreeNode node, int currMax, int currMin){
        if(node == null){
            return;
        }
        int currMaxDiff = Math.max(Math.abs(currMax - node.val), Math.abs(currMin - node.val));
        result = Math.max(result, currMaxDiff);
        currMax = Math.max(currMax, node.val);
        currMin = Math.min(currMin, node.val);
        dfs(node.left, currMax, currMin);
        dfs(node.right, currMax, currMin);    
        return;
    }
    
    public int maxAncestorDiff(TreeNode root) {
        if(root == null){
            return 0;
        }
        dfs(root, root.val, root.val);
        return result;
    }
    
    
}[/code]