aboutsummaryrefslogtreecommitdiff
path: root/other/longest_zigzag_bt.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/longest_zigzag_bt.cpp')
-rw-r--r--other/longest_zigzag_bt.cpp46
1 files changed, 46 insertions, 0 deletions
diff --git a/other/longest_zigzag_bt.cpp b/other/longest_zigzag_bt.cpp
new file mode 100644
index 0000000..b0ebe7f
--- /dev/null
+++ b/other/longest_zigzag_bt.cpp
@@ -0,0 +1,46 @@
+// 1372. Longest ZigZag Path in a Binary Tree
+#include "leetcode.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
+ */
+
+class Solution {
+ int ans = 0;
+ map<pair<TreeNode *, bool>, int> mp;
+ int find(TreeNode *root, bool check) {
+ if (mp.find({root, check}) != mp.end())
+ return mp[{root, check}];
+ if (check) {
+ if (root->right)
+ return mp[{root, check}] = 1 + find(root->right, !check);
+ else if (root->left)
+ return mp[{root, check}] = 1 + find(root->left, !check);
+ }
+ return mp[{root, check}] = 1;
+ }
+ void preorder(TreeNode *root) {
+ if (root) {
+ if (root->left)
+ ans = max(ans, find(root->left, true));
+ if (root->right)
+ ans = max(ans, find(root->right, false));
+ preorder(root->left);
+ preorder(root->right);
+ }
+ }
+
+public:
+ int longestZigZag(TreeNode *root) {
+ preorder(root);
+ return ans;
+ }
+};