diff options
Diffstat (limited to 'other/longest_zigzag_bt.cpp')
-rw-r--r-- | other/longest_zigzag_bt.cpp | 46 |
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; + } +}; |