http://www.nowcoder.com/question/next?pid=1597148&qid=44665&tid=3119680

對于一棵由黑白點組成的二叉樹，我們需要找到其中最長的單色簡單路徑，其中簡單路徑的定義是從樹上的某點開始沿樹邊走不重復的點到樹上的另一點結束而形成的路徑，而路徑的長度就是經(jīng)過的點的數(shù)量(包括起點和終點)。而這里我們所說的單色路徑自然就是只經(jīng)過一種顏色的點的路徑。你需要找到這棵樹上最長的單色路徑。
給定一棵二叉樹的根節(jié)點(樹的點數(shù)小于等于300，請做到O(n)的復雜度)，請返回最長單色路徑的長度。這里的節(jié)點顏色由點上的權值表示，權值為1的是黑點，為0的是白點。

測試用例:
[0,0,1,1,0,0,1,1,1,0,0,1]
對應輸出應該為:4
你的輸出為:5

解答;

1. 記憶化搜索；
   2）注意符號的優(yōu)先級。。。逗號運算符。。。

import java.util.*;

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}*/
public class LongestPath {
/*
    記憶化搜索；
    每個節(jié)點植被搜索一次
    */
Map<TreeNode,Integer> blkMap = new HashMap<>();
    Map<TreeNode,Integer> whtMap = new HashMap<>();
    Integer maxPath = 0;

    public int findPath(TreeNode root) {
        // write code here
        if(root == null) return 0;
        dfsNode(root);
        return maxPath;
    }

    private void dfsNode(TreeNode root){
        blkPath(root);
        whtPath(root);
        if(root.left != null) dfsNode(root.left);
        if(root.right != null) dfsNode(root.right);
    }

    private int blkPath(TreeNode root){
        if(root.val == 0){
            blkMap.put(root,0);
            return 0;
        }
        int left = 0, right = 0;
        if(root.left != null){
            if(blkMap.get(root.left) == null)
                blkPath(root.left);
            left = blkMap.get(root.left);
        }
        if(root.right!= null){
            if(blkMap.get(root.right) == null)
                blkPath(root.right);
            right = blkMap.get(root.right);
        }
        /*
        ldft -> root -> right
        */
        int path = 1 + left + right;
        maxPath = maxPath >= path ? maxPath:path;
        /*
        parent -> root -> [left|right]
        */
        int maxChild = 1 + (left >= right ? left:right);
        blkMap.put(root,maxChild);
        return maxChild;
    }

    private int whtPath(TreeNode root){
        if(root.val == 1){
            whtMap.put(root,0);
            return 0;
        }

        int left = 0, right = 0;
        if(root.left != null){
            if(whtMap.get(root.left) == null)
                whtPath(root.left);
            left = whtMap.get(root.left);
        }
        if(root.right!= null){
            if(whtMap.get(root.right) == null)
                whtPath(root.right);
            right = whtMap.get(root.right);
        }
        /*
        ldft -> root -> right
        */
        int path = 1 + left + right;
        maxPath = maxPath >= path ? maxPath:path;
        /*
        parent -> root -> [left|right]
        */
        int maxChild = 1 + (left >= right ? left:right);
        whtMap.put(root,maxChild);
        return maxChild;
    }
}