leetcode1372

 1 class Solution {
 2     int maxpath = 0;
 3     HashMap<TreeNode, Integer> map1 = new HashMap<TreeNode, Integer>();
 4     HashMap<TreeNode, Integer> map2 = new HashMap<TreeNode, Integer>();
 5 
 6     public void preOrder(TreeNode node) {
 7         if (node != null) {
 8             int leftpath = getTreePath(node, 0, 0);
 9             int rightpath = getTreePath(node, 1, 0);
10             maxpath = Math.max(maxpath, Math.max(leftpath, rightpath));
11 
12             preOrder(node.left);
13             preOrder(node.right);
14         }
15     }
16 
17     public int getTreePath(TreeNode node, int direction, int pathsum) {
18         if (node == null) {
19             return 0;
20         } else {
21             if (direction == 0) {// 向左
22                 if (map1.containsKey(node)) {
23                     return pathsum + map1.get(node);
24                 } else {
25                     pathsum = getTreePath(node.left, 1, pathsum) + 1;
26                     map1.put(node, pathsum);
27                     return pathsum;
28                 }
29             } else {// 向右
30                 if (map2.containsKey(node)) {
31                     return pathsum + map2.get(node);
32                 } else {
33                     pathsum = getTreePath(node.right, 0, pathsum) + 1;
34                     map2.put(node, pathsum);
35                     return pathsum;
36                 }
37             }
38         }
39 
40     }
41 
42     public int longestZigZag(TreeNode root) {
43         preOrder(root);
44         return maxpath - 1;
45     }
46 }

算法思路：二叉树遍历+备忘录缓存。

maxpath记录全局最大的蛇形走位的路径长度，map1记录从某个节点开始左向的最大长度(缓存)，map2记录从某个节点开始右向的最大长度(缓存)。

使用某序遍历整个输，对每一个节点，依次执行左向走法和右向走法，并更新最大全局路径(第10行)。

注意22行和30行，分别是用缓存加速查询，如果之前已经查询过的节点，就直接返回。