How to Compute the Maximum Difference Between Node and Ancestor?
- 时间:2020-09-20 14:08:18
- 分类:网络文摘
- 阅读:74 次
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.)
Binary tree
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) —
推荐阅读:回顾历史,自强不息作文500字 儿童节游必胜客作文 生活 感恩 由误解所想到的作文450字 我的家乡周口作文 三下乡中的失误和反省 六年级感恩父亲节作文1000字 手工纸剪小树数学题:用一张长45cm、宽21cm的手工纸,能剪几棵这样的小树? 数学题:两人轮流报数,每次只能报1或2,把两人报的所有数加起来 数学题:下面三位同学要去量身高、验视力,每项检查都要3分钟
- 评论列表
-
- 添加评论