【树】B040_LC_节点与其祖先之间的最大差值（后序遍历）

一、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(n)，
• 空间复杂度：$O(1)$O(1)，