题目
给你一棵以 root 为根的二叉树，二叉树中的交错路径定义如下：
选择二叉树中 任意 节点和一个方向（左或者右）。
如果前进方向为右，那么移动到当前节点的的右子节点，否则移动到它的左子节点。
改变前进方向：左变右或者右变左。
重复第二步和第三步，直到你在树中无法继续移动。
交错路径的长度定义为：访问过的节点数目 - 1（单个节点的路径长度为 0 ）。
请你返回给定树中最长 交错路径 的长度。
示例 1：
输入：root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]
输出：3
解释：蓝色节点为树中最长交错路径（右 -> 左 -> 右）。
示例 2：
输入：root = [1,1,1,null,1,null,null,1,1,null,1]
输出：4
解释：蓝色节点为树中最长交错路径（左 -> 右 -> 左 -> 右）。
示例 3：
输入：root = [1]
输出：0
分析
仍然是每一个节点都遍历，遍历时根据向左或向右的规则，来计数最长路径
题解
class Solution {
int max;
public int longestZigZag(TreeNode root) {
// 递归，需要每个节点都跑一次，取最大值
if(root == null){
return 0;
}
max = 0;
// 根节点，还没走，所以第三个参数路径长度是0，
findWay(root, 0, 0);
findWay(root, 1, 0);
return max;
}
// 节点node，走了左w=0，或者右w=1，走的路径长度n
public void findWay(TreeNode node, int w, int n){
// 最大路径
max = Math.max(n, max);
// 左为0，表示上一步走了左，进入左之后也要判断下一步的左和右，是否重新开始
if(w == 0){
// 上一步走左，这里走右，同时路径长度+1
if(node.right != null){
findWay(node.right, 1, n+1);
}
// 上一步走左，但这里没有右子树，只能继续走左，长度置0，但要加上到达下一个节点的长度1
if(node.left != null){
findWay(node.left, 0, 1);
}
}else{
// 上一步为右，这里走左n+1，走右0+1
if(node.left != null){
findWay(node.left, 0, n+1);
}
if(node.right != null){
findWay(node.right, 1, 1);
}
}
}
}
