find-mode-in-binary-search-tree

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Given the <code>root</code> of a binary search tree (BST) with duplicates, return all the <a href="https://en.wikipedia.org/wiki/Mode_(statistics)" target="_blank">mode(s)</a> (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:

<ul>
	<li>The left subtree of a node contains only nodes with keys less than or equal to the node&#39;s key.</li>
	<li>The right subtree of a node contains only nodes with keys greater than or equal to the node&#39;s key.</li>
	<li>Both the left and right subtrees must also be binary search trees.</li>
</ul>

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/11/mode-tree.jpg" style="width: 142px; height: 222px;" />
<pre>
Input: root = [1,null,2,2]
Output: [2]
</pre>

Example 2:

<pre>
Input: root = [0]
Output: [0]
</pre>

&nbsp;
Constraints:

<ul>
	<li>The number of nodes in the tree is in the range <code>[1, 104]</code>.</li>
	<li><code>-105 &lt;= Node.val &lt;= 105</code></li>
</ul>

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

findMode

Find Mode in Binary Search Tree

Validate Binary Search Tree

validate-binary-search-tree

验证二叉搜索树

Tree

Depth-First Search

Binary Search Tree

Binary Tree

给你一个含重复值的二叉搜索树（BST）的根节点 <code>root</code> ，找出并返回 BST 中的所有 <a href="https://baike.baidu.com/item/%E4%BC%97%E6%95%B0/44796" target="_blank">众数</a>（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

<ul>
	<li>结点左子树中所含节点的值 小于等于 当前节点的值</li>
	<li>结点右子树中所含节点的值 大于等于 当前节点的值</li>
	<li>左子树和右子树都是二叉搜索树</li>
</ul>

&nbsp;

示例 1：
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/11/mode-tree.jpg" style="width: 142px; height: 222px;" />
<pre>
输入：root = [1,null,2,2]
输出：[2]
</pre>

示例 2：

<pre>
输入：root = [0]
输出：[0]
</pre>

&nbsp;

提示：

<ul>
	<li>树中节点的数目在范围 <code>[1, 104]</code> 内</li>
	<li><code>-105 &lt;= Node.val &lt;= 105</code></li>
</ul>

&nbsp;

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