blob: e5f1e9d5580cf4c953e00aeb22f6fc32905ef0d1 (
plain)
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
|
// 1372. Longest ZigZag Path in a Binary Tree
#include <math.h>
#include <stdlib.h>
/*
* given the 'root' of a binary tree. a zigzag path for a binary tree is defined
* as follows
* - choose any node in the binary tree and a direction (left or right)
* - if the current direction is right, move to the right child of the current
* node
* - change the direction from right to left or from left to right
* - repeat the second nd third steps until you cannot move in the tree
* zigzag length is defined as the number of nodes visited - 1. return longest
* zigzag
*/
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
typedef struct {
int left;
int right;
} data;
data process(struct TreeNode *root, int *max) {
data res;
if (!root) {
res.left = -1;
res.right = -1;
return res;
}
data l_tree = process(root->left, max);
data r_tree = process(root->right, max);
res.left = 1 + r_tree.right;
res.right = 1 + l_tree.left;
*max = fmax(fmax(res.left, *max), res.right);
return res;
}
int longestZigZag(struct TreeNode *root) {
int max = 0;
process(root, &max);
return max;
}
|