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.

/**
 * 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
}

• 相关文章
• 全局相关文章