[두 갈래 나무] 501.Find Mode in Binary Search Tree

제목: 501.Find Mode in Binary Search Tree
Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST. Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than or equal to the node's key. The right subtree of a node contains only nodes with keys greater than or equal to the node's key. Both the left and right subtrees must also be binary search trees.

For example:Given BST [1,null,2,2]
  1 
    \
     2
   /
 2

return [2]

Note: If a tree has more than one mode, you can return them in any order. Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).
최대 횟수의value를 되돌려주는 두 갈래 검색 트리첫 번째 생각은 HashMap으로 중량도 조사할 수 있고 횟수도 계산할 수 있지만 follow up의 추가 공간 요구에 부합되지 않고 두 갈래 검색 트리의 성질도 이용하지 않는다는 것이다.
그럼 교체야.두 갈래 검색 트리에 대해 중차 반복을 사용하면 값이 작은 것부터 큰 것까지 반복할 수 있습니다.이렇게 같은value는 필연적으로 연결되어 이전value와 다른node를 만나면 이전value가 가장 많은 value인지 비교할 수 있다.
그런데 이 문제의 함정과 주의해야 할 점이 너무 많아요!
1. 여러 개의 횟수가 같은value가 나타날 수 있지만 몇 개가 있을지 모르기 때문에list로 잠시 저장합니다.예를 들어 이런 경우: [1,1,2,null,null,null,2]2.마지막value의 횟수 판단은 주 함수로 돌아가야 합니다. 후속적으로node가 없으면 helper에서 그 횟수가 가장 많은지 아닌지를 판정할 수 없기 때문에preMax,value,cnt,resList 변수는 전역 변수가 됩니다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private List resList = new ArrayList();
    public int cnt = -1; //so for the first node, cnt != preMax; Must be global vriable, to suitble for last node
    private int value = Integer.MAX_VALUE;
    private int preMax = 0;
    
    public int[] findMode(TreeNode root) {
        
        helper(root);//Left tree
        
        //check if last value should be added
        if(cnt > preMax){
            resList.clear();
            resList.add(value);//add the Previous value
        }else if(cnt == preMax){
            resList.add(value);
        }
        
        int len = resList.size();
        int[] out = new int[len];
        for(int i =0 ;i< len; i++){
            out[i] = resList.get(i);
        }
        return out;
        
    }
    private void helper(TreeNode node){
        if(node == null) return;
        helper(node.left);//Left tree
           
        if(node.val != value){
            if(cnt > preMax){
                resList.clear();
                resList.add(value);//add the Previous value
                preMax = cnt; 
            }else if(cnt == preMax){
                resList.add(value);//add the Previous value
            }
            value = node.val;
            cnt = 1;//it must be the first new value
        }else{
            cnt++;
        }
        helper(node.right);//Right tree
    }
}