题目大意：
二叉树中的最长交错路径
给你一棵以 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
提示：
- 每棵树最多有
50000个节点。 - 每个节点的值在
[1, 100]之间。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1372
解题思路分析：
这道题我们还是需要dfs二叉树的每条路径，去寻找最长的交错路径。dfs时我们需要传递一个变量isLeft来判断当前路线是该走左分支还是右分支。dfs函数中我们有两种选择，首先如果isLeft是true并且左分支又不为空，那么可以选择dfs到左分支，此时交叉路径长度加一，同时isLeft变为false。另外一种选择是，若当前节点的右分支若不为空，我们可以以当前节点为起点，新建一条交叉路径，即dfs至右分支，交叉路径长度还原为1（当前节点到右子节点长度），isLeft变为true。每一步dfs中，我们都需要用当前交叉路径的长度与全局最大长度进行比较，dfs完所有路径后，最大长度即是返回结果。
实现代码：
int res=0; // 返回结果
public int longestZigZag(TreeNode root) {
// dfs所有路径
dfs(root,0,false);
return res;
}
void dfs(TreeNode root, int count, boolean isLeft){
// 更新全局最大长度
res=Math.max(res, count);
// 如果当前交叉路径该走左子节点
if(isLeft){
// 若左子节点不为空
if(root.left!=null){
// dfs到左子节点，
// 交叉路径长度加一
// 下一步该走右子节点
dfs(root.left,count+1,false);
}
// 以当前节点为起点统计另一条路线
// 如果右子节点不为空
if(root.right!=null){
// dfs到右子节点，
// 交叉路径长度为一
// 下一步该走左子节点
dfs(root.right,1,true);
}
}else{ // 如果当前交叉路径该走右子节点
// 若右子节点不为空
if(root.right!=null){
// dfs到右子节点，
// 交叉路径长度加一
// 下一步该走左子节点
dfs(root.right,count+1,true);
}
// 以当前节点为起点统计另一条路线
// 如果左子节点不为空
if(root.left!=null){
// dfs到左子节点，
// 交叉路径长度为一
// 下一步该走右子节点
dfs(root.left,1,false);
}
}
}本题解法执行时间为4ms。
Runtime: 4 ms, faster than 100.00% of Java online submissions for Longest ZigZag Path in a Binary Tree.
Memory Usage: 53.3 MB, less than 100.00% of Java online submissions for Longest ZigZag Path in a Binary Tree.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1372-longest-zigzag-path-in-a-binary-tree-解题思路分析/