1372二叉树中的最长交错路径

给你一棵以 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] 之间。

Solution 1

/**
 * 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 {
    public int longestZigZag(TreeNode root) {
        Map<TreeNode, int[]> map = new HashMap<>();
        int[] nullLengthLR = { -1, -1 };
        map.put(null, nullLengthLR);
        int maxLength = Integer.MIN_VALUE;
        traverse(root, map);
        for (Map.Entry<TreeNode, int[]> entry : map.entrySet()) {
            TreeNode node = entry.getKey();
            getlengthLR(node, map);
            int[] lengthLR = entry.getValue();
            maxLength = Integer.max(maxLength, lengthLR[0]);
            maxLength = Integer.max(maxLength, lengthLR[1]);
        }
        return maxLength;
    }

    void traverse(TreeNode node, Map<TreeNode, int[]> map) {
        if (node == null) {
            return;
        }
        int[] lengthLR = new int[2];
        lengthLR[0] = Integer.MIN_VALUE;
        lengthLR[1] = Integer.MIN_VALUE;
        map.put(node, lengthLR);
        traverse(node.left, map);
        traverse(node.right, map);
    }

    void getlengthLR(TreeNode node, Map<TreeNode, int[]> map) {
        int[] lengthLR = map.get(node);
        if (lengthLR[0] == Integer.MIN_VALUE || lengthLR[1] == Integer.MIN_VALUE) {
            getlengthLR(node.left, map);
            getlengthLR(node.right, map);
            lengthLR[0] = map.get(node.left)[1] + 1;
            lengthLR[1] = map.get(node.right)[0] + 1;
        }
    }
}