Re: [閒聊] 每日LeetCode

作者: Rushia (みけねこ的鼻屎)   2022-12-09 11:24:43
1026. Maximum Difference Between Node and Ancestor
給予一個二元樹,找出最大的值v,v為兩個相異的節點a和b之值相減之絕對值,a必須
滿足他是b的祖先節點(A node a is an ancestor of b if either: any child of a is equal to b or any
child of a is an ancestor of b.)。
Example:
https://assets.leetcode.com/uploads/2020/11/09/tmp-tree.jpg
Input: root = [8,3,10,1,6,null,14,null,null,4,7,13]
Output: 7
Explanation: We have various ancestor-node differences, some of which are
given below :
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
...
Among all possible differences, the maximum value of 7 is obtained by |8 - 1|
= 7.
思路:
1.可以用dfs遍歷所有節點,並記錄父節點的最大值和最小值,最大的絕對值差一定是
當前節點減去最大或最小。
Java Code:
作者: pandix (麵包屌)   2022-12-09 11:32:00
大師
作者: DDFox (冒險者兼清潔工)   2022-12-09 11:37:00
大師
作者: sustainer123 (caster)   2022-12-09 11:42:00
大師

Links booklink

Contact Us: admin [ a t ] ucptt.com