day18
1.530.二叉搜索树的最小绝对差:依然是利用二叉搜索树中序遍历得到的结点是有序的特性,对其进行递归中序遍历,并采用双指针法得到两个结点间的绝对差(中序遍历得到的有序数组中相邻两个结点间的绝对差一定是最小的,不需要再去与更远的结点进行比较,只需要比较两两相邻间的差值就够了),最后通过对绝对差进行不断更新就能获得最小绝对差。
2.501.二叉搜索树中的众数: 递归中序遍历,双指针比较前后两个结点是否相等,同时更新maxValue,当count==maxValue时,将该元素加入到结果集中。如果count>maxValue,要注意更新maxValue的值,并清空结果集(失效)。注意递归过程中这些值都要是全局变量。
3.236.二叉树的最近公共祖先:递归后序遍历,
//左右子树都不为空,说明找到了pq,此时root就是最近公共祖先
if(left != NULL && right != NULL) return root;
//当一边找了了p/q,就直接返回这边的结点,
//当层层递归结束,要么会只返回这个结点(这个结点本身就是最近公共祖先)
//要么会与另外一支汇合,分别作为左右结点返回值,最后返回他们此时的根节点
if(left != NULL && right == NULL) return left;
else if(left == NULL && right != NULL) return right;
else return NULL;
这两天被文本查询卡住了,有点烦躁,把权游八季的解说看完了,现在心静下来了,后面继续刷算法,搞完这个文本查询就开始学STL了。不要放弃!
2.501.二叉搜索树中的众数: 递归中序遍历,双指针比较前后两个结点是否相等,同时更新maxValue,当count==maxValue时,将该元素加入到结果集中。如果count>maxValue,要注意更新maxValue的值,并清空结果集(失效)。注意递归过程中这些值都要是全局变量。
3.236.二叉树的最近公共祖先:递归后序遍历,
//左右子树都不为空,说明找到了pq,此时root就是最近公共祖先
if(left != NULL && right != NULL) return root;
//当一边找了了p/q,就直接返回这边的结点,
//当层层递归结束,要么会只返回这个结点(这个结点本身就是最近公共祖先)
//要么会与另外一支汇合,分别作为左右结点返回值,最后返回他们此时的根节点
if(left != NULL && right == NULL) return left;
else if(left == NULL && right != NULL) return right;
else return NULL;
这两天被文本查询卡住了,有点烦躁,把权游八季的解说看完了,现在心静下来了,后面继续刷算法,搞完这个文本查询就开始学STL了。不要放弃!
全部评论
相关推荐
查看26道真题和解析
点赞 评论 收藏
分享
点赞 评论 收藏
分享