# 1372. Longest ZigZag Path in a Binary Tree
###### tags: `Leetcode` `Bloomberg` `DFS`
## 思路
递归
对于每个node，分别求从它的left和right child zigzag走下去能走多远，过程中记录最长的
## Code

class Solution {
    int maxLen = 0;
    //dir == true left
    //dir == false right
    public int longestZigZag(TreeNode root) {
        int leftLen = 0, rightLen = 0;
        if(root.left!=null) leftLen = dfs(root.left, false)+1;
        if(root.right!=null) rightLen = dfs(root.right, true)+1;
        return Math.max(maxLen, Math.max(leftLen, rightLen));
    }
    public int dfs(TreeNode root, boolean dir){
        int leftLen = 0, rightLen = 0;
        
        if(dir){
            if(root.left!=null) leftLen = dfs(root.left, !dir)+1;
            if(root.right!=null) rightLen = dfs(root.right, dir)+1;
        }
        else{
            if(root.right!=null) rightLen = dfs(root.right, !dir)+1;
            if(root.left!=null) leftLen = dfs(root.left, dir)+1;
        }
        maxLen = Math.max(maxLen, Math.max(leftLen, rightLen));
        return dir?leftLen:rightLen;
    }
}