tags: leetcode medium Tree Depth-First Search Binary Tree

1026. Maximum Difference Between Node and Ancestor

Description

Given the root of a binary tree, find the maximum value v for which there exist 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.

Examples

Example1

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.

Example2

Input: root = [1,null,2,null,0,3]
Output: 3

Constraints:

• The number of nodes in the tree is in the range [2, 5000].
• $0 \leq Node.val \leq 10^5$

Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
typedef struct TreeNode TNODE;
int postOrder(TNODE *root, int max, int min){
    if(!root) return max-min;
    max = (root->val > max) ? root->val : max;
    min = (root->val < min) ? root->val : min;
    int left = postOrder(root->left, max, min);
    int right = postOrder(root->right, max, min);
    return left>right ? left : right;
}

int maxAncestorDiff(struct TreeNode* root){
    if(!root) return 0;
    return postOrder(root, root->val, root->val);
}

Complexity

Space	Time
$O(N)$	$O(N)$

Result

• Runtime : 0 ms, 100%
• Memory : 7.5 MB, 54.55%

Notes

• Each difference is founded by the maximum and minimum of the path.
• Since each branch has the same subset notes of their parent, they inherit their parent’s maximum and minimum and continue to update.
• We can not using call by address, because we need to maintain previous( parents’ ) max/min for next branch counting.
• We use DFS( post-order traversal ) to scan whole tree, update max/min as we found NULL pointer. After then we just update the difference of current branch to parent and ancestors and they will compare their branches and return maximum difference.