Given the root of a binary tree, find the maximum value V for which there exists 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: [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.Note:
The number of nodes in the tree is between 2 and 5000.
Each node will have value between 0 and 100000.
Depth First Search Algorithm to Find the Maximum Difference Between Node and Ancestor of a Given Binary Tree
We can utilise a helper function which pass down the min and max value for the current sub tree. Then, at any time, we can update the answer by storing the maximum of (max – min).
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 | /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int maxAncestorDiff(TreeNode* root) { if (root == nullptr) return 0; dfs(root, root->val, root->val); return ans; } private: int ans = 0; void dfs(TreeNode* root, int small, int big) { if (root == nullptr) return; big = max(big, root->val); small = min(small, root->val); int cur = big - small; ans = max(ans, cur); dfs(root->left, small, big); dfs(root->right, small, big); } }; |
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int maxAncestorDiff(TreeNode* root) { if (root == nullptr) return 0; dfs(root, root->val, root->val); return ans; } private: int ans = 0; void dfs(TreeNode* root, int small, int big) { if (root == nullptr) return; big = max(big, root->val); small = min(small, root->val); int cur = big - small; ans = max(ans, cur); dfs(root->left, small, big); dfs(root->right, small, big); } };
The above C++ code implements the Depth First Search Algorithm in Recursion fashion. And the answer is stored globally. It can be also passed as a reference parameter.
The algorithm runs at O(N) complexity in both time and space where N is the number of nodes in the binary tree. We can however, make the recursive DFS function return the result for the subtree, thus, making the code a little bit concise and easy to understand/follow.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int maxAncestorDiff(TreeNode* root) { if (root == nullptr) return 0; return dfs(root, root->val, root->val); } private: int dfs(TreeNode* root, int small, int big) { if (root == nullptr) return big - small; big = max(big, root->val); small = min(small, root->val); return max(dfs(root->left, small, big), dfs(root->right, small, big)); } }; |
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int maxAncestorDiff(TreeNode* root) { if (root == nullptr) return 0; return dfs(root, root->val, root->val); } private: int dfs(TreeNode* root, int small, int big) { if (root == nullptr) return big - small; big = max(big, root->val); small = min(small, root->val); return max(dfs(root->left, small, big), dfs(root->right, small, big)); } };
The terminating condition for the recursive helper function is the difference value between the min and max value that is passed TOP-down from the root of the binary tree.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: How to Compute the Day of the Year?
Next Post: How to Find Words That Can Be Formed by Characters?