leetcode

commit ab9cd2da44c7062aa21fda6d76cc031923032c8b
parent 496ccdcd72dbb90958ff2fffbbcb9c013fb8e36a
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Wed, 19 Apr 2023 13:29:48 +0200

Daily Problem

Diffstat:
A
Problems/1372.cpp
 | 
19
+++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 20 insertions(+), 0 deletions(-)
diff --git a/Problems/1372.cpp b/Problems/1372.cpp
@@ -0,0 +1,19 @@
+class Solution {
+  int res = 0;
+
+  int dfs(TreeNode *root, bool zig) {
+    if (!root) return -1;
+
+    int left = dfs(root->left, false);
+    int right = dfs(root->right, true);
+    res = max(res, max(left + 1, right + 1));
+
+    return zig ? left + 1 : right + 1;
+  }
+
+public:
+  int longestZigZag(TreeNode *root) {
+    dfs(root, false);
+    return res;
+  }
+};
diff --git a/README.md b/README.md
@@ -423,6 +423,7 @@ for solving problems.
 |  1346  |    Easy    | [Check if N and Its Double Exist](Problems/1346.cpp)                                             |
 |  1361  |   Medium   | [Validate Binary Tree Nodes](Problems/1361.cpp)                                                  |
 |  1367  |   Medium   | [Linked List in Binary Tree ](Problems/1367.cpp)                                                 |
+|  1372  |   Medium   | [Longest ZigZag Path in a Binary Tree](Problems/1372.cpp)                                        |
 |  1373  |    Hard    | [Maximum Sum BST in Binary Tree](Problems/1373.cpp)                                              |
 |  1379  |    Easy    | [Find a Corresponding Node of a Binary Tree in a Clone of That Tree](Problems/1379.cpp)          |
 |  1382  |   Medium   | [Balance a Binary Search Tree](Problems/1382.cpp)                                                |