题目链接及描述

1372. 二叉树中的最长交错路径 - 力扣（LeetCode）

题目分析

        题目所述，计算在二叉树中交替遍历的最大深度【左->右->左】【右->左->右】，例如对于从当前根节点root出发，则此时遍历方向有两个，左、右，同时当前路径走向影响下一步路径的走向（下一步路径走向必须和当前这一步路径走向相反）为了实现这个功能，编写一个方法，传入当前根节点的同时，传入一个标志位 flag，根据标志位判断 flag 的走向。

• 若：flag == 1，则此步走向为left，同时递归调用时传入 -flag。实现转向的功能。
• 同理：若：flag == -1，则此步走向为 right，同时递归调用时传入 -flag。

        编写函数实现如下：

    public int getMaxPaths(TreeNode root, int flag){
        if(root == null){
            return 0;
        }
        int ans = 0;
        if(flag == 1){
            ans = 1 + getMaxPaths(root.left, -flag);
        }else if(flag == -1){
            ans = 1 + getMaxPaths(root.right, -flag);
        }
        return ans;
    }

         上面所述函数可以计算出当前节点 root ，在flag 分别为 1 和 -1 时对应的最大交替深度。

        此时编写整体代码如下：

class Solution {
    public int longestZigZag(TreeNode root) {
        if(root == null){
            return 0;
        }
        int ans = Math.max(getMaxPaths(root, 1), getMaxPaths(root, -1)) - 1;
        return Math.max(ans, Math.max(longestZigZag(root.left), longestZigZag(root.right)));
    }
    public int getMaxPaths(TreeNode root, int flag){
        if(root == null){
            return 0;
        }
        int ans = 0;
        if(flag == 1){
            ans = 1 + getMaxPaths(root.left, -flag);
        }else if(flag == -1){
            ans = 1 + getMaxPaths(root.right, -flag);
        }
        return ans;
    }
}

         如果此前对二叉树的递归调用有所了解，很容易发现此种写法中存在大量的冗余调用：

        对于上图中所示节点，在此树的遍历过程中就会被调用三次，节点越靠近下面，被重复调用的次数就越多，同时随着树的深度的增大，被循环调用的节点个数也会越来越多。

         运行上面所写代码，不难发现代码超时，并不能通过所有的测试用例。

        如何优化：借助HashMap，将已经遍历到的节点的最大交错深度存储起来，此时又产生了新的问题，对于当前某节点 cur 而言，他的运行方向有左和右，显示将 cur 作为HashMap的key存储起来并不能达到想要的效果，此时如果设计key ，进一步思考可以将 root + "_" + flag 作为HashMap的 key，value 为对应的交错深度，这样完美解决了某个 Key 对应遍历有左、右两种情况的场景。

代码编写

class Solution {
    public Map<Object, Integer> map = new HashMap<>();
    public int longestZigZag(TreeNode root) {
        if(root == null){
            return 0;
        }
        int ans = Math.max(getMaxPaths(root, 1), getMaxPaths(root, -1)) - 1;
        return Math.max(ans, Math.max(longestZigZag(root.left), longestZigZag(root.right)));
    }
    public int getMaxPaths(TreeNode root, int flag){
        if(map.containsKey(root + "_" + flag)){
            return map.get(root + "_" + flag);
        }
        if(root == null){
            return 0;
        }
        int ans = 0;
        if(flag == 1){
            ans = 1 + getMaxPaths(root.left, -flag);
        }else if(flag == -1){
            ans = 1 + getMaxPaths(root.right, -flag);
        }
        map.put(root + "_" + flag, ans);
        return ans;
    }
}