给定二叉树的根节点 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 得出。
我们不需要维护每个节点的最大差值,只需要维护一条路径上的最大元素和最小元素就够了,外加一个深度优先遍历。
class Solution {
public:
int ans=0;
void dfs(TreeNode* node,int mn,int mx){
if(node==nullptr)return ;
mn=min(mn,node->val);
mx=max(mx,node->val);
ans=max(ans,max(node->val-mn,mx-node->val));
dfs(node->right,mn,mx);
dfs(node->left,mn,mx);
}
int maxAncestorDiff(TreeNode* root) {
dfs(root,root->val,root->val);
return ans;
}
};
标签:node,1026,val,mn,mx,差值,root,节点 From: https://www.cnblogs.com/Liubox/p/18115788