# 501. Find Mode in Binary Search Tree

總是先算

````java
```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }

maxCnt
currCnt
prev
result

if (currCnt > maxCnt) {
    result.clear();
    result.add(node.val);
} else if (currCnt == maxCnt) {
    result.add(node.val);
}


1 2 1 2 3 1 2 3
1 1 2 2 2 3 3 3

 */
class Solution {
    int maxCnt = 0;  // 2
    int currCnt = 1; // 2
    Integer prev = null;  //2
    // result [2]

    public int[] findMode(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        dfs(root, result);
        return result.stream().mapToInt(i -> i).toArray();
    }
    private void dfs(TreeNode node, List<Integer> result) {
        if (node == null) {
            return;
        }
        dfs(node.left, result);

        if (prev != null) {
            if (prev != node.val) { 
                currCnt = 1;
            } else {
                currCnt++;
            }
        }
        if (currCnt > maxCnt) {
            maxCnt = currCnt;
            result.clear();
            result.add(node.val);
        } else if (currCnt == maxCnt) {
            result.add(node.val);
        }
        prev = node.val;

        dfs(node.right, result);
    }
}
```
````



後算

````java
```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
/**
maxCnt: 3
currCnt: 3
result: [1] -> [2]
prev

if currCnt == maxCnt add result
if currCnt > maxCnt clear result, add curr elemnt
  2
    0.  3              
1 1 2 2 2. 3 3 3

 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int maxCnt = 0;
    int currCnt = 1;
    Integer prev = null;
    public int[] findMode(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        dfs(root, result);
        helper(result);

        int[] rs = new int[result.size()];
        for (int i = 0; i < rs.length; i++) {
            rs[i] = result.get(i);
        }
        return rs;
    }
    private void dfs(TreeNode node, List<Integer> result) {
        if (node == null) {
            return;
        }
        dfs(node.left, result);
        // 1 1 2 2 2. 3 3 3
        if (prev != null) {
            if (prev != node.val) {
                helper(result);
            } else {
                currCnt++;
            }
        }

        prev = node.val;
        dfs(node.right, result);
    }
    private void helper(List<Integer> result) {
        if (currCnt > maxCnt) {
            maxCnt = currCnt;
            result.clear();
            result.add(prev);
        } else if (currCnt == maxCnt) {
            result.add(prev);
        }
        currCnt = 1;
    }
}

/*
邊走邊算

*/
```
````
