Leetcode 687. 最长同值路径

最长同值路径

描述：

给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。

注意：两个节点之间的路径长度由它们之间的边数表示。

示例：

题解：

一、 递归求解

class Solution {
    int max=Integer.MIN_VALUE;
    public int longestUnivaluePath(TreeNode root) {
        if(root==null) return 0;
        UnivaluePath(root);

        return max;
    }
    public  int UnivaluePath(TreeNode root) {
　　　　　　//terminator
          if(root==null) return 0;
　　　　　　//第一次遇到drill into 在最前面//drill into  
          int left=UnivaluePath(root.left);//获取左右节点的路径长
          int righ=UnivaluePath(root.right);
　　　　　　//process logic 处理逻辑
          int ledir=0,ridir=0;
          if(root.left!=null&&root.left.val==root.val)//如果相同，则父节点路径需加上子节点的
              ledir+= left+1;
        if(root.right!=null&&root.right.val==root.val)
            ridir+= righ+1;
        max=Math.max(max,ledir+ridir);//最长路径
        return Math.max(ledir,ridir);//返回较长的路径
    }
}

二、深度优先求解

/**
 * Problem
 *      687.Longest Univalue Path
 * Grade of difficulty
 *      Easy
 * Related topics
 *      98. Validate Binary Search Tree
 *      110.Balanced Binary Tree
 *      111.Minimum Depth of Binary Tree
 *      129.Sum Root to Leaf Numbers
 *      144.Binary Tree Preorder Traversal
 * @author cartoon
 * @version 1.0
 */
class Solution {
    
    private int max;
    
    /**
     * 1.About Complexity
     *     1.1 Time Complexity is O(n)
     *     1.2 Space Complexity is O(n)
     * 2.how I solve
     *     2.1 this solution is base on depth traversal
     *     2.2 static left and right children tree's depth,and at the same time judge current node's val is same as parent's val
     * 3.About submit record
     *     3.1 9ms and 51.8MB memory in LeetCode China
     *     3.2 3ms and 40.5MB memory in LeetCode
     * 4.Q&A
     * @param root
     * @return
     */
    public int longestUnivaluePath(BinaryTreeNode root) {
        if(root==null){
            return 0;
        }
        postOrder(root,root.val);
        return max;
    }

    private int postOrder(BinaryTreeNode root,int val){
        if(root==null){
            return 0;
        }
        int left=postOrder(root.left,root.val);
        int right=postOrder(root.right,root.val);
        max=Math.max(max,left+right);
        if(root.val==val){
            return Math.max(left,right)+1;
        }
        return 0;
    }
}