Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //first approach
- class Solution {
- public:
- int pathLength = 0;
- void dfs(TreeNode* node, int left, int right) {
- if (node == nullptr) {
- return;
- }
- pathLength = max({pathLength, left,right});
- dfs(node->right,0,left+1);
- dfs(node->left, right+1, 0);
- }
- int longestZigZag(TreeNode* root) {
- dfs(root, 0, 0);
- return pathLength;
- }
- };
- // second approach
- class Solution {
- public:
- int pathLength = 0;
- void dfs(TreeNode* node, bool goLeft, int steps) {
- if (node == nullptr) {
- return;
- }
- pathLength = max(pathLength, steps);
- if (goLeft) {
- dfs(node->left, false, steps + 1);
- dfs(node->right, true, 1);
- } else {
- dfs(node->left, false, 1);
- dfs(node->right, true, steps + 1);
- }
- }
- int longestZigZag(TreeNode* root) {
- dfs(root, false, 0);
- dfs(root, true, 0);
- return pathLength;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement