share my java O(N) solution!


  • 0
    T
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        int maxNumNodes = 1;
        public int longestUnivaluePath(TreeNode root) {
            if(root == null){
                return 0;
            }
            
            helper(root);
            return maxNumNodes-1;
        }
        
        public int helper(TreeNode root){
            if(root.left==null&&root.right==null){
                return 1;
            }
            
            int left = 0;
            int numOfNodes = 1;
            if(root.left!=null){
                int temp_left = helper(root.left);
                if(root.val==root.left.val){
                    left=temp_left;
                    numOfNodes+=left;
                }
            }
            int right = 0;
            if(root.right!=null){
                int temp_right = helper(root.right);
                if(root.val==root.right.val){
                    right = temp_right;
                    numOfNodes+=right;
                }
            }
            
            maxNumNodes=Math.max(maxNumNodes,numOfNodes);
            return left>right?(1+left):(1+right);
        }
    }
    

  • 0
    This post is deleted!

  • 0
    T

    @Ren-W why? I went through every node of the tree only one time, right?


  • 0

    @tiandiao123
    I made a mistake. You are right. You visit every node once only.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.