Leetcode - Maximum Difference Between Node and Ancestor
https://leetcode.com/problems/maximum-difference-between-node-and-ancestor/
Given the root of a binary tree, find the maximum value V for which there exists different nodes A and B where V = |A.val - B.val| and A is an ancestor of 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 1:
Input: [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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */func maxAncestorDiff(root *TreeNode) int { result := 0 find(root, &result,root.Val, root.Val) return result}func find(root *TreeNode, result *int, maxNum, minNum int) { if root == nil { return } *result = max(*result, abs(minNum - root.Val)) *result = max(*result, abs(maxNum - root.Val)) if root.Left != nil { find(root.Left, result, max(maxNum, root.Left.Val), min(minNum, root.Left.Val)) } if root.Right != nil { find(root.Right, result, max(maxNum, root.Right.Val), min(minNum, root.Right.Val)) }}func max(a, b int) int { if a > b { return a } return b}func min(a, b int) int { if a < b { return a } return b}func abs(a int) int { if a < 0 { return 0 - a } return a} |
评论 (0)
