数组递归

若它的左子树不空则左子树上所有结点的值均小于它的根结点的值若它的右子树不空则右子树上所有结点的值均大于它的根结点的值它的左、右子树也分别为二叉搜索树

递归法

递归函数的参数传入的就是根节点和要搜索的数值返回的就是以这个搜索数值所在的节点代码如下

TreeNode*

因为二叉搜索树的节点是有序的所以可以有方向的去搜索。

如果root-val

val搜索左子树如果root-val

};因为搜索到了目标节点所以要立即返回这样才符合找到节点就返回的逻辑搜索某一条边如果不加return那么就是遍历整棵树了。

迭代法

因为二叉搜索树的特殊性也就是节点的有序性可以不使用辅助栈或者队列就可以写出迭代法。

对于二叉搜索树不需要回溯的过程因为节点的有序性就帮我们确定了搜索的方向。

例如要搜索元素为3的节点我们不需要搜索其他节点也不需要做回溯查找的路径已经规划好了。

//迭代法

节点的左子树只包含小于当前节点的数。

节点的右子树只包含大于当前节点的数。

所有左子树和右子树自身必须也是二叉搜索树。

示例1

中序遍历下输出的二叉搜索树节点的数值是有序序列。

有了这个特性验证二叉搜索树就相当于变成了判断一个序列是不是递增的了。

思路1可以递归中序遍历将二叉搜索树转变成一个数组然后只要比较一下这个数组是否是有序即可注意二叉搜索树中不能有重复元素。

递归遍历把数据存入数组

{traversal(root);//判断数组是否单增for(int

result.size();

}以上代码中把二叉树转变为数组来判断是最直观的但其实不用转变成数组可以在递归遍历的过程中直接判断是否有序。

这道题目比较容易陷入两个陷阱

不能单纯的比较左节点小于中间节点右节点大于中间节点就完事了写出了类似这样的代码

(root-val

可能是int的最小值如果这样使用最小的int来比较也是不行的此时可以初始化比较元素为longlong的最小值。

双指针

要定义一个longlong的全局变量用来比较遍历的节点是否有序即上一个节点的值递归函数返回bool类型供上一个节点因此递归函数为

long

遍历到空节点返回假设如果就是空节点那是二叉搜索树因此返回true代码如下

//假设为空嘛

root-val就返回false注意元素相同时候也要返回false代码如下

bool

那如果后台测试数据有longlong的最小值呢无法再初始化一个更小的值了吧建议避免初始化最小值使用双指针的办法快慢指针首先取到最左面节点数值每次快指针与之前的值做比较即可。

/**************双指针优化****************/

TreeNode*

可以用迭代法模拟二叉树中序遍历且与遍历普通二叉树模板类似迭代法中序遍历稍加改动就可以了变成二叉搜索树迭代模板代码如下:

bool

NULL)return;traversal(node-left);

//右

其实在二叉搜素树中序遍历的过程中我们就可以直接计算了需要用一个pre节点记录一下cur节点的前一个节点。

代码如下

NULL)return;traversal(node-left);

//左//中if(pre

可以用迭代法模拟二叉树中序遍历且与遍历普通二叉树模板类似迭代法中序遍历稍加改动就可以了在遍历中加入前一个节点的指针并不断判断更新最小差值即可代码如下:

/****************迭代法***************/

int

遇到在二叉搜索树上求什么最值求差值之类的都要思考一下二叉搜索树可是有序的要利用好这一特点。

同时要学会在递归遍历的过程中如何记录前后两个指针这也是一个小技巧学会了还是很受用的。

力扣原题链接501.

如果不是二叉搜索树最直观的方法一定是把这个树都遍历了用map统计频率把频率排个序最后取前面高频的元素的集合。

具体步骤如下

至于用前中后序哪种遍历也不重要因为就是要全遍历一遍这里采用前序遍历代码如下

mapint,

C中只能根据map的key进行排序无法对value排序所以要把map转化数组即vector再进行排序当然vector里面放的也是对组

pairint,

此时数组vector中已经是存放着按照频率排好序的pair那么把前面高频的元素取出来就可以了代码如下

for(int

//判断出现频率最大的几个数result.push_back(vec[i].first);

}整体C代码如下

resMap.end());sort(vec.begin(),

vec.end(),

//判断出现频率最大的几个数result.push_back(vec[i].first);

//把频率最大的几个数存入结果数组elsebreak;}return

result;

}遍历有序数组的元素出现频率从头遍历相邻两个元素作比较然后就把出现频率最高的元素输出就可以了。

弄一个指针指向前一个节点这样每次cur当前节点才能和pre前一个节点作比较。

pre

应该是先遍历一遍数组找出最大频率maxCount然后再重新遍历一遍数组把出现频率为maxCount的元素放进集合但这种方式遍历了两遍数组。

每次频率最大的数都放进结果集若出现更大的频率的数更新整个结果集清空结果集并把最大频率的数放到结果集

count

如果和最大值相同放进result中result.push_back(cur-val);

}频率

maxCount而且要清空结果集因为结果集之前的元素都失效了if

(count

很关键的一步不要忘记清空result之前result里的元素都失效了result.push_back(cur-val);

/********思路2

NULL)return;traversal(node-left);

//左if(pre

//更新旧指针/**********核心细节代码区****************/if(cnt

maxCnt)

//收获频率最大的数res.push_back(node-val);else

if(cnt

之前存入的结果都作废res.push_back(node-val);

//当前新的长度的数记得存进去}traversal(node-right);

//右

只要把中序遍历转成迭代中间节点的处理逻辑完全一样直接粘贴代码的即可

/********思路3

//更新旧指针/**********核心细节代码区****************/if(cnt

maxCnt)

//收获频率最大的数res.push_back(cur-val);else

if(cnt

之前存入的结果都作废res.push_back(cur-val);

cur-right;