欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-04-27 11:34:50
...

一、Problem

给定二叉树的根节点 root,找出存在于不同节点 A 和 B 之间的最大值 V,其中 V = |A.val - B.val|,且 A 是 B 的祖先。

(如果 A 的任何子节点之一为 B,或者 A 的任何子节点是 B 的祖先,那么我们认为 A 是 B 的祖先)
【树】B040_LC_节点与其祖先之间的最大差值(后序遍历)

输入:[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)
相关标签: # 树 后序遍历