一、题目
1、题目描述
给定二叉树的根节点
root
,找出存在于 不同 节点A
和B
之间的最大值V
,其中V = |A.val - B.val|
,且A
是B
的祖先。(如果 A 的任何子节点之一为 B,或者 A 的任何子节点是 B 的祖先,那么我们认为 A 是 B 的祖先)
2、接口描述
python3
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
cpp
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int maxAncestorDiff(TreeNode* root) {
}
};
3、原题链接
二、解题报告
1、思路分析
我们从根往下dfs,维护路径上的最大值ma最小值mi,当遇到空节点时,我们用ma - mi维护最大差值
2、复杂度
时间复杂度: O(n)空间复杂度:O(n),递归栈开销
3、代码详解
python3
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
ret = 0
def dfs(rt: Optional[TreeNode], mi: int, ma: int) -> None:
if not rt:
nonlocal ret
ret = max(ret, ma - mi)
return
ma = max(ma, rt.val)
mi = min(mi, rt.val)
dfs(rt.left, mi, ma)
dfs(rt.right, mi, ma)
dfs(root, root.val, root.val)
return ret
cpp
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int maxAncestorDiff(TreeNode* root) {
int ret = 0;
function<void(TreeNode*, int, int)> dfs = [&](TreeNode* rt, int mi, int ma){
if(!rt) {
ret = max(ret, ma - mi);
return;
}
dfs(rt->left, min(mi, rt->val), max(rt->val, ma));
dfs(rt->right, min(mi, rt->val), max(rt->val, ma));
};
dfs(root, root->val, root->val);
return ret;
}
};