leetcode

Leetcode Solutions (0x6A73)
git clone https://git.pngu.org/leetcode
Log | Files | Refs | Submodules | README

max_diff_node_ancestor.c (1488B)

 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
49
// 1026. Maximum Difference Between Node and Ancestor
#include "leetcode.h"

/*
 * 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 ancesotr of 'b'. a node 'a' is an ancesotr of 'b' if either any child if
 * 'a' is equal to 'b' or any child 'a' is an ancestor of 'b'.
 */

struct TreeNode {
  int val;
  struct TreeNode *left;
  struct TreeNode *right;
};

int helper(struct TreeNode *node, int min_seen, int max_seen) {
  int leftdiff, rightdiff;
  if (!(node->val < min_seen || node->val > max_seen))
    ;
  else {
    if (node->val > max_seen)
      max_seen = node->val;
    else
      min_seen = node->val;
  }
  int diff = max_seen - min_seen;
  if (node->left == NULL && node->right == NULL)
    return diff;
  else if (!(node->left != NULL && node->right != NULL)) {
    if (node->left == NULL) {
      leftdiff = 0;
      rightdiff = helper(node->right, min_seen, max_seen);
      return (rightdiff > diff ? rightdiff : diff);
    } else {
      rightdiff = 0;
      leftdiff = helper(node->left, min_seen, max_seen);
      return (leftdiff > diff ? leftdiff : diff);
    }
  } else {
    leftdiff = helper(node->left, min_seen, max_seen);
    rightdiff = helper(node->right, min_seen, max_seen);
    return leftdiff > rightdiff ? leftdiff : rightdiff;
  }
}

int maxAncestorDiff(struct TreeNode *root) {
  return !root ? 0 : helper(root, root->val, root->val);
}