1026. Maximum Difference Between Node and Ancestor LeetCode Solution
In this guide, you will get 1026. Maximum Difference Between Node and Ancestor LeetCode Solution with the best time and space complexity. The solution to Maximum Difference Between Node and Ancestor problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(h)
1026. Maximum Difference Between Node and Ancestor LeetCode Solution in C++
class Solution {
public:
int maxAncestorDiff(TreeNode* root) {
return maxAncestorDiff(root, root->val, root->val);
}
private:
// Returns |the maximum - the minimum| of the tree.
int maxAncestorDiff(TreeNode* root, int mn, int mx) {
if (root == nullptr)
return 0;
mn = min(mn, root->val);
mx = max(mx, root->val);
const int l = maxAncestorDiff(root->left, mn, mx);
const int r = maxAncestorDiff(root->right, mn, mx);
return max({mx - mn, l, r});
}
}; /* code provided by PROGIEZ */
1026. Maximum Difference Between Node and Ancestor LeetCode Solution in Java
class Solution {
public int maxAncestorDiff(TreeNode root) {
return maxAncestorDiff(root, root.val, root.val);
}
// Returns |the maximum - the minimum| of the tree.
private int maxAncestorDiff(TreeNode root, int mn, int mx) {
if (root == null)
return 0;
mn = Math.min(mn, root.val);
mx = Math.max(mx, root.val);
final int l = maxAncestorDiff(root.left, mn, mx);
final int r = maxAncestorDiff(root.right, mn, mx);
return Math.max(mx - mn, Math.max(l, r));
}
} // code provided by PROGIEZ
1026. Maximum Difference Between Node and Ancestor LeetCode Solution in Python
