엔지니어 게시판
LeetCode 솔루션 분류

[interview] 1026. Maximum Difference Between Node and Ancestor

컨텐츠 정보

본문

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

관련자료

댓글 3

mingki님의 댓글

  • 익명
  • 작성일
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);
    }
};

학부유학생님의 댓글

  • 익명
  • 작성일
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)

Coffee님의 댓글

  • 익명
  • 작성일
/**
 * 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;
    }
    
    
}
전체 396 / 1 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


  • 현재 접속자 178 명
  • 오늘 방문자 2,727 명
  • 어제 방문자 5,332 명
  • 최대 방문자 11,134 명
  • 전체 회원수 1,047 명
알림 0