Question

501. Find Mode in Binary Search Tree

中文文档

Description

Given the root of a binary search tree (BST) with duplicates, return _all the mode(s) (i.e., the most frequently occurred element) in it_.

If the tree has more than one mode, return them in any order.

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.

 

Example 1:

Input: root = [1,null,2,2]
Output: [2]

Example 2:

Input: root = [0]
Output: [0]

 

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• -105 <= Node.val <= 105

 

Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).

Solutions

Solution 1

# Definition for a binary tree node.
# class TreeNode:
#   def __init__(self, val=0, left=None, right=None):
#     self.val = val
#     self.left = left
#     self.right = right
class Solution:
  def findMode(self, root: TreeNode) -> List[int]:
    def dfs(root):
      if root is None:
        return
      nonlocal mx, prev, ans, cnt
      dfs(root.left)
      cnt = cnt + 1 if prev == root.val else 1
      if cnt > mx:
        ans = [root.val]
        mx = cnt
      elif cnt == mx:
        ans.append(root.val)
      prev = root.val
      dfs(root.right)

    prev = None
    mx = cnt = 0
    ans = []
    dfs(root)
    return ans

/**
 * 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;
 *   }
 * }
 */
class Solution {
  private int mx;
  private int cnt;
  private TreeNode prev;
  private List<Integer> res;

  public int[] findMode(TreeNode root) {
    res = new ArrayList<>();
    dfs(root);
    int[] ans = new int[res.size()];
    for (int i = 0; i < res.size(); ++i) {
      ans[i] = res.get(i);
    }
    return ans;
  }

  private void dfs(TreeNode root) {
    if (root == null) {
      return;
    }
    dfs(root.left);
    cnt = prev != null && prev.val == root.val ? cnt + 1 : 1;
    if (cnt > mx) {
      res = new ArrayList<>(Arrays.asList(root.val));
      mx = cnt;
    } else if (cnt == mx) {
      res.add(root.val);
    }
    prev = root;
    dfs(root.right);
  }
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *   int val;
 *   TreeNode *left;
 *   TreeNode *right;
 *   TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *   TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *   TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
  TreeNode* prev;
  int mx, cnt;
  vector<int> ans;

  vector<int> findMode(TreeNode* root) {
    dfs(root);
    return ans;
  }

  void dfs(TreeNode* root) {
    if (!root) return;
    dfs(root->left);
    cnt = prev != nullptr && prev->val == root->val ? cnt + 1 : 1;
    if (cnt > mx) {
      ans.clear();
      ans.push_back(root->val);
      mx = cnt;
    } else if (cnt == mx)
      ans.push_back(root->val);
    prev = root;
    dfs(root->right);
  }
};

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */
func findMode(root *TreeNode) []int {
  mx, cnt := 0, 0
  var prev *TreeNode
  var ans []int
  var dfs func(root *TreeNode)
  dfs = func(root *TreeNode) {
    if root == nil {
      return
    }
    dfs(root.Left)
    if prev != nil && prev.Val == root.Val {
      cnt++
    } else {
      cnt = 1
    }
    if cnt > mx {
      ans = []int{root.Val}
      mx = cnt
    } else if cnt == mx {
      ans = append(ans, root.Val)
    }
    prev = root
    dfs(root.Right)
  }
  dfs(root)
  return ans
}

public class Solution {
  private int mx;
  private int cnt;
  private TreeNode prev;
  private List<int> res;

  public int[] FindMode(TreeNode root) {
    res = new List<int>();
    Dfs(root);
    int[] ans = new int[res.Count];
    for (int i = 0; i < res.Count; ++i) {
      ans[i] = res[i];
    }
    return ans;
  }

  private void Dfs(TreeNode root) {
    if (root == null) {
      return;
    }
    Dfs(root.left);
    cnt = prev != null && prev.val == root.val ? cnt + 1 : 1;
    if (cnt > mx) {
      res = new List<int>(new int[] { root.val });
      mx = cnt;
    } else if (cnt == mx) {
      res.Add(root.val);
    }
    prev = root;
    Dfs(root.right);
  }
}