营销型公司网站建设,分析网站建设前期的seo准备工作,大量网站开发视频 文档VIP资源,没有网站也可以做cpa1. 题目
给定二叉树的根节点 root#xff0c;找出存在于不同节点 A 和 B 之间的最大值 V#xff0c;其中 V |A.val - B.val|#xff0c;且 A 是 B 的祖先。
#xff08;如果 A 的任何子节点之一为 B#xff0c;或者 A 的任何子节点是 B 的祖先#xff0c;那么我们认为…1. 题目
给定二叉树的根节点 root找出存在于不同节点 A 和 B 之间的最大值 V其中 V |A.val - B.val|且 A 是 B 的祖先。
如果 A 的任何子节点之一为 B或者 A 的任何子节点是 B 的祖先那么我们认为 A 是 B 的祖先 示例
输入[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 到 5000 之间。
每个节点的值介于 0 到 100000 之间。来源力扣LeetCode 链接https://leetcode-cn.com/problems/maximum-difference-between-node-and-ancestor 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
深度优先搜索从根节点到每个叶子节点记录到当前位置的最大最小值达到叶子节点时做差取abs最大的
class Solution {int maxdiff 0;
public:int maxAncestorDiff(TreeNode* root) {dfs(root,root-val,root-val);return maxdiff;}void dfs(TreeNode* root, int MAX, int MIN) {if(!root){maxdiff max(maxdiff, abs(MAX-MIN));return;}int MA max(root-val, MAX);int MI min(root-val, MIN);dfs(root-left,MA,MI);dfs(root-right,MA,MI);}
};
