//Recursive 1-pass in-order traversal solution: save the ans in an ArrayList first
//Time: O(n), 2ms
//Space: O(n), when input is 1,2,3,4,...,n-2,n-1,n-1
class Solution {
    int currVal;
    int currCount = 0;
    int maxCount = 0;

    public int[] findMode(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        DFS(root, list);
        int[] ans = new int[list.size()];
        for(int i = 0; i < ans.length; i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }

    private void DFS(TreeNode root, ArrayList<Integer> list) {
        if(root == null) return;
        DFS(root.left, list);
        handleValue(root.val, list);
        DFS(root.right, list);
    }

    private void handleValue(int val, ArrayList<Integer> list) {
        if(val != currVal) {
            currVal = val;
            currCount = 0;
        }
        currCount++;
        if(currCount > maxCount) {
            list.clear();
            list.add(val);
            maxCount = currCount;
        } else if(currCount == maxCount) {
            list.add(val);
        }
    }
}
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */