My java O(1) space solution 4ms one pass inorder traversal


  • 0
    L

    the temp[0] record the current val,
    the temp[1] record the occurrences of current val,
    the temp[2] record the max occurrences.

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public int[] findMode(TreeNode root) {
            List<Integer> res = new ArrayList<Integer>();
            if(root == null) return new int[0];
            int[] temp = new int[3];
            helper(root, res, temp);
            if(temp[1] == temp[2]){
                res.add(temp[0]);
            }
            else if(temp[1] > temp[2]){
                res = new ArrayList<Integer>();
                res.add(temp[0]);
            }
            int[] out = new int[res.size()];
            for(int i = 0; i < res.size(); ++i) out[i] = res.get(i);
            return out;
        }
        public void helper(TreeNode root, List<Integer> res, int[] temp){
            if(root == null) return;
            helper(root.left, res, temp);
            
            if(temp[1] == 0){
                temp[0] = root.val;
                temp[1] = 1;
            }
            else if(root.val == temp[0]){
                temp[1]++;
            }
            else{
                if(temp[1] == temp[2]){
                    res.add(temp[0]);
                }
                else if(temp[1] > temp[2]){
                    res.clear();
                    res.add(temp[0]);
                    temp[2] = temp[1];
                }
                temp[0] = root.val;
                temp[1] = 1;
            }
            helper(root.right, res, temp);
        }
    }
    

Log in to reply
 

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