给定二叉树的根节点 root
,找出存在于 不同 节点 A
和 B
之间的最大值 V
,其中 V = |A.val - B.val|
,且 A
是 B
的祖先。
(如果 A 的任何子节点之一为 B,或者 A 的任何子节点是 B 的祖先,那么我们认为 A 是 B 的祖先)
示例 1:
输入:root = [8,3,10,1,6,null,14,null,null,4,7,13] 输出:7 解释: 我们有大量的节点与其祖先的差值,其中一些如下: |8 - 3| = 5 |3 - 7| = 4 |8 - 1| = 7 |10 - 13| = 3 在所有可能的差值中,最大值 7 由 |8 - 1| = 7 得出。
示例 2:
输入:root = [1,null,2,null,0,3] 输出:3
提示:
- 树中的节点数在
2
到5000
之间。 0 <= Node.val <= 105
直接DFS,遍历过程中维护当前路径的最大最小值即可
1 /** 2 * Definition for a binary tree node. 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode() : val(0), left(nullptr), right(nullptr) {} 8 * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} 9 * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} 10 * }; 11 */ 12 class Solution { 13 public: 14 int max_difference = INT32_MIN; 15 void travel(TreeNode* root, int maximum, int minimum){ 16 maximum = max(maximum, root->val); 17 minimum = min(minimum, root->val); 18 max_difference = max(max_difference, maximum - minimum); 19 if (root != nullptr && root->left != nullptr){ 20 travel(root->left,maximum,minimum); 21 } 22 if (root != nullptr && root->right != nullptr){ 23 travel(root->right,maximum,minimum); 24 } 25 26 } 27 int maxAncestorDiff(TreeNode* root) { 28 travel(root,INT32_MIN,INT32_MAX); 29 return max_difference; 30 } 31 };