FindModeInBinarySearchTreeOPT [source code]

public class FindModeInBinarySearchTreeOPT {
static
/******************************************************************************/
public class Solution {
    public int[] findMode(TreeNode root) {
        ArrayList<Integer> ret = new ArrayList<>();
        int[] count = new int[1];
        int[] max_count = new int[1];
        count[0] = 1;

        if (root == null) return new int[0];

        TreeNode last = help(root, ret, count, max_count, null);
        if (count[0] > max_count[0]) {
            ret.clear();
            ret.add(last.val);
        } else if (count[0] == max_count[0]) {
            ret.add(last.val);
        }

        int[] res = new int[ret.size()];
        for (int i=0; i<ret.size(); i++) {
            res[i] = ret.get(i);
        }

        return res;
    }

    TreeNode help(TreeNode root, ArrayList<Integer> ret, int[] count, int max_count[], TreeNode pre) {
        if (root.left != null) {
            pre = help(root.left, ret, count, max_count, pre);
        }

        if (pre != null) {
            if (pre.val == root.val) {
                count[0]++;
            } else {
                if (count[0] == max_count[0]) {
                    ret.add(pre.val);
                } else if (count[0] > max_count[0]) {
                    max_count[0] = count[0];
                    ret.clear();
                    ret.add(pre.val);
                }
                count[0] = 1;
            }
        }   

        // System.out.println("Current: " + root.val + " max: " + max_count[0] + " count " + count[0]);
        if (root.right != null) {
            return help(root.right, ret, count, max_count, root);
        }

        return root;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        FindModeInBinarySearchTreeOPT.Solution tester = new FindModeInBinarySearchTreeOPT.Solution();
    }
}

这个是 submission 最优解: 7(74);

Problem Description

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).

Difficulty:Easy
Category:Algorithms
Acceptance:37.96%
Contributor: Coder_1215
Companies
google
Related Topics
tree
Similar Questions
Validate Binary Search Tree