面试题54:二叉搜索树的第k个结点 给定一棵二叉搜索树,请找出其中的第k大的结点。 左边都比中间小,右边都比中间大,所以用中序遍历(左中右)就可以实现按结点的值从小到大遍历,遍历时候进行计数即可。 #include<bits/stdc++.h> #include "../Utilities/BinaryTree.h" using namespace std; //递归函数:输入二叉(子)树根,输入k,在其上找中序遍历(剩下的)第k个结点 //k用引用传递,其改变可以影响到上面的递归层,k在调用中每找到一…

2018年10月23日 0条评论 3点热度 阅读全文

最近在读《剑指Offer》,在作者的GitHub上能找到全部源码,包含测试用例,但注释极少。光是读思路也是纸上得来终觉浅,自己拉到本地运行,一行行地解读一下。 算法一直是自己的弱项之一,不可马虎。 数组问题 数组的时间效率很高,可以根据下标在O(1)的时间读写任何元素;数组的空间效率不是很好,经常会有空闲的区域没有得到充分利用。 面试题3:数组中重复的数字 长度为n的数组中所有数字都在0~n-1的范围内,找出数组中任意一个重复的数字。 如果数组中没有重复的数字,那么从小到大排序后第i位置应是数字i。从头到尾扫描这个…

2018年9月3日 0条评论 4点热度 阅读全文