【树】B040

一、Problem

给定二叉树的根节点 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 之间。

二、Solution

方法一：后序遍历

很容易想到通过后序遍历返回左右子树的最值，为什么是最值呢？因为求的两节点之差的绝对值的最大值，

ps：这里我直接用了 C++ 写的，感觉真的很方便啊，大爱 C++

class Solution { public: int ans; typedef pair<int, int> pii; pair<int, int> dfs(TreeNode* root) { if (root == NULL) return pair(INT_MAX, INT_MIN); pii l = dfs(root->left); pii r = dfs(root->right); int mi = min({root->val, l.first, r.first}); int ma = max({root->val, l.second, r.second}); ans = max({ans, root->val-mi, ma-root->val}); return pair(mi, ma); } int maxAncestorDiff(TreeNode* root) { dfs(root); return ans; } };

复杂度分析

时间复杂度：$O(n)$，空间复杂度：$O(1)$，