1372. Longest ZigZag Path in a Binary Tree

You are given the root of a binary tree.

A ZigZag path for a binary tree is defined as follow:

• Choose any node in the binary tree and a direction (right or left).
• If the current direction is right, move to the right child of the current node; otherwise, move to the left child.
• Change the direction from right to left or from left to right.
• Repeat the second and third steps until you can't move in the tree.

Zigzag length is defined as the number of nodes visited - 1. (A single node has a length of 0).

Return the longest ZigZag path contained in that tree.

Example 1:

Input: root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]
Output: 3
Explanation: Longest ZigZag path in blue nodes (right -> left -> right).

Example 2:

Input: root = [1,1,1,null,1,null,null,1,1,null,1]
Output: 4
Explanation: Longest ZigZag path in blue nodes (left -> right -> left -> right).

Example 3:

Input: root = [1]
Output: 0

题目：给定一棵二叉树，找其中最长的zigzag路。

思路：递归，zigzag路不一定从根节点开始，因此需要记录以每个节点开始的最长zigzag路径，从底部往上回溯。因此从上往下时需要用direction(dir)记录每个节点是左节点还是右节点。如果是左节点（-1代表左节点），则从底部往上时需选择右子节点的zigzag路，如果是右节点（1代表右节点），则需选择其左子节点的zigzag路。根节点用0代表，则选择左子节点或右子节点最长的那条路。代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int helper(TreeNode* node, int& res, int dir){
        if(!node) return 0;
        int l = helper(node->left, res, -1);
        int r = helper(node->right, res, 1);
        res = max(res, max(l+1, r+1));
        if(dir == -1) return r+1;
        if(dir == 1) return l+1;
        return max(l,r)+1;
    }
    int longestZigZag(TreeNode* root) {
        int res = 0;
        helper(root, res, 0);
        return res-1;
    }
};