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.
Top-down
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 class Solution { int res = 0 ; pair<int , int > dfs (TreeNode* node) { int mi = node->val; int ma = node->val; if (node->left) { auto [lmi, lma] = dfs (node->left); mi = min (mi, lmi); ma = max (ma, lma); res = max ({res, abs (node->val - mi), abs (node->val - ma)}); } if (node->right) { auto [rmi, rma] = dfs (node->right); mi = min (mi, rmi); ma = max (ma, rma); res = max ({res, abs (node->val - mi), abs (node->val - ma)}); } return {mi, ma}; } public : int maxAncestorDiff (TreeNode* root) { dfs (root); return res; } };
Bottom-up
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution {public : int maxAncestorDiff (TreeNode* root, int mi = 100000 , int ma = 0 ) { if (!root) return ma - mi; mi = min (mi, root->val); ma = max (ma, root->val); return max (maxAncestorDiff (root->left, mi, ma), maxAncestorDiff (root->right, mi, ma)); } };