1026. Maximum Difference Between Node and Ancestor¶
题目信息¶
- 题号:
1026
- 难度:
Medium
- 主题:
二叉树、祖先关系、最大绝对差
- 原题:
- 重点:
只比较存在严格祖先关系的两个不同节点,计算节点值绝对差并返回全树最大值
题目重述¶
给定一棵非空二叉树。若节点 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。