1026. Maximum Difference Between Node and Ancestor

题目信息

题号:

1026

难度:

Medium

主题:

二叉树、祖先关系、最大绝对差

原题:

LeetCode 1026

重点:

只比较存在严格祖先关系的两个不同节点,计算节点值绝对差并返回全树最大值

题目重述

给定一棵非空二叉树。若节点 a 位于从根到节点 b 的路径上,并且 a 与 b 不是同一节点,则 a 是 b 的祖先。

在所有满足祖先关系的节点对 (a, b) 中,计算 |a.val - b.val|,并返回能够得到的最大绝对差。

树中节点数在 [2, 5000] 范围内,0 <= Node.val <= 10^5。

自建示例

最大差来自根节点和深层后代:

输入:root = [5,2,9,1,4,7,12]
输出:7
解释:值为 5 的根节点是值为 12 的节点的祖先,两者差为 7;树中不存在更大的祖先与后代值差。

祖先和后代的值完全相同:

输入:root = [4,4]
输出:0
解释:唯一祖先节点对的两个值都为 4,绝对差为 0。