1372. Longest ZigZag Path in a Binary Tree-蒲公英云

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;
    }
};