https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/

难度：简单

---

  给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。

假定 BST 有如下定义：

• 结点左子树中所含结点的值小于等于当前结点的值

• 结点右子树中所含结点的值大于等于当前结点的值

• 左子树和右子树都是二叉搜索树

例如：

  给定 BST [1,null,2,2],

1
 \
  2
 /
2

  返回 [2]

提示：如果众数超过1个，不需考虑输出顺序

进阶： 你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

---

解法1：中序遍历

  对于一棵二叉搜索树，若对其进行中序遍历并在遍历过程中顺序记录节点值，那么记录的值会是一个单调递增序列（在本题中是单调不减序列）。

  这样的话，若要求众数，我们可以先对其进行中序遍历，众数在序列中的位置一定是连续的，如 [1, 2, 2, 2, 3]。这样，我们对这个序列进行遍历并计数，就能够得到它的众数。

  不过，为了避免使用额外空间，我们可以在遍历过程中就求出众数，具体做法是维护一个 max ，表示当前所遇到的最多的连续数字的个数，然后在遍历过程中累计每个数字出现的次数，若比 max 大，则使用当前数字覆盖结果数组，并更新 max 值。

  在中序遍历完成之后，我们还需要最后进行一次众数判断，因为最后的连续数字不会在遍历过程中判断是否是众数。

JS 代码：

var findMode = function(root) {
    let res = [];
    if (!root) {
        return res;
    }
    let n;
    let count = 0;
    let max = -1;

    const dfs = (node) => {
        if (!node) {
            return;
        }

        dfs(node.left);
        
        if (n === undefined) {
            n = node.val;
            count = 1;
        } else if (n === node.val) {
            count++;
        } else { // 遇到新的数字
            if (count > max) {
                max = count;
                res = [n];
            } else if (count === max) {
                res.push(n);
            }
            n = node.val;
            count = 1;
        }    
        dfs(node.right);
    };

    dfs(root);

    if (count > max) {
        max = count;
        res = [n];
    } else if (count === max) {
        res.push(n);
    }

    return res;
};

C 版本：

int max;
int count;
int cur;

void dfs(struct TreeNode* root, int* res, int* returnSize) {
    if (!root) {
        return;
    }

    dfs(root->left, res, returnSize);
    
    if (count == -1) {
        cur = root->val;
        count = 1;
    } else if (cur == root->val) {
        count++;
    } else {
        if (max < count) {
            max = count;
            *returnSize = 0;
            res[(*returnSize)++] = cur;
        } else if (max == count) {
            res[(*returnSize)++] = cur;
        }

        cur = root->val;
        count = 1;
    }

    dfs(root->right, res, returnSize);
}

int* findMode(struct TreeNode* root, int* returnSize){
    *returnSize = 0;
    int *res = malloc(sizeof(int) * 4001);

    count = -1;
    max = -1;

    if (!root) {
        return res;
    }

    dfs(root, res, returnSize);

    if (max < count) {
        max = count;
        *returnSize = 0;
        res[(*returnSize)++] = cur;
    } else if (max == count) {
        res[(*returnSize)++] = cur;
    }

    return res;
}

解法2：Morris 算法

  所有能使用中序遍历解决的问题都能使用 Morris 算法来优化其空间复杂度。

  Morris 算法详情可看

  在使用 Morris 算法时最重要的是要把握好节点遍历的时机。

var findMode = function(root) {
    let res = [];
    if (!root) {
        return res;
    }
    let n;
    let count = 0;
    let max = -1;

    let pre;

    const check = () => {
        if (max < count) {
            max = count;
            res = [n];
        } else if (max === count) {
            res.push(n);
        }
    };

    while (root) {
        if (root.left) {
            pre = root.left;
            while (pre.right && pre.right !== root) {
                pre = pre.right;
            }

            if (!pre.right) {
                pre.right = root;
                root = root.left;
            } else { 
                // 此时是刚从左孩子节点返回之后，往右孩子遍历
                if (n === undefined) {
                    n = root.val;
                    count = 1;
                } else if (n === root.val) {
                    count++;
                } else {
                    check();
                    n = root.val;
                    count = 1;
                }
                pre.right = null;
                root = root.right;
            }
        } else {
           	// 节点此时可能是借助前面设置的空闲指针返回父节点，也可能是从父节点到右节点遍历的过程
            if (n === undefined) {
                n = root.val;
                count = 1;
            } else if (n === root.val) {
                count++;
            } else {
                check();
                n = root.val;
                count = 1;
            }
            root = root.right;
        }
    }

    check();

    return res;
};