Java solution with Morris Traversal


  • 0
    public class Solution {
        
        private List<Integer> mode = new ArrayList<Integer>();
        private int count=0;
        private int max=0;
        private Integer pval=null;
        
        public int[] findMode(TreeNode root) {
            
            if(root==null) return new int[0];
            //Morris Traversal
            TreeNode rootl=null;
            while(root!=null){
                if(root.left==null){
                    updateList(root.val);
                    root=root.right;
                }
                else{
                    rootl=root.left;
                    while(rootl.right!=null && rootl.right!=root) rootl=rootl.right;
                    
                    if(rootl.right==root){
                        rootl.right=null;
                        updateList(root.val);
                        root=root.right;
                    }
                    else{
                        rootl.right=root;
                        root=root.left;
                    }
                }
            }
            //end of Morris Traversal
            
            //convert list to array
            int[] r = new int[mode.size()];
            for(int i=0;i<r.length;i++) r[i]=mode.get(i);
            
            return r;
            
        }
        private void updateList(int v){
            if(pval==null || v!=pval) count=0;
            count++;
            if(count>max){
                max=count;
                mode.clear();
                mode.add(v);
            }
            else if(count==max){
                mode.add(v);
            }
            
            pval=v;
        }
    }
    

Log in to reply
 

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