1372. Longest ZigZag Path in a Binary Tree

• Longest ZigZag Path in a Binary Tree
• 给一棵树，对于每个节点查找最长的 Zig-Zag 长度

思路

• 因为 Zig-Zag Path 是在一个连续往下的情况，所以考虑深度优先
• 因为每次往左走下一次必须向右走，所以设置 dfs 函数的参数为private void dfs(TreeNode node, boolean goLeft, int steps)
• The terminal condition is: node == null: return
• 在 dfs 中，每次遇到符合条件的情况（左右/右左）让 step+1，同时设置左左/右右情况的 step 为 1
• 在 main 中分别对于一开始往左走和一开始往右走的情况进行递归
• 每次递归结束前的最后一次的 step 就是最长的 zig-zag 长度
• - LeetCode Editorial

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int longestPath = 0;
    private void dfs(TreeNode node, boolean goLeft, int steps){
        if(node == null){
            return;
        }

        longestPath = Math.max(longestPath, steps);

        if(goLeft){
            dfs(node.left, false, steps + 1);
            dfs(node.right, true, 1);
        }
        else{
            dfs(node.right, true, steps + 1);
            dfs(node.left, false, 1);
        }
    }
    public int longestZigZag(TreeNode root) {
        dfs(root, false, 0);
        dfs(root, true, 0);
        return longestPath;
    }
}