阅读目录
- 翻转二叉树(输出二叉树的镜像)
- 求二叉树中最远两个结点的距离
- 二叉树的深度
- 求二叉树中两个结点的最近公共祖先
- 由前序遍历和中序遍历重建二叉树
- 反转单链表
- 二分查找
- 判断一个字符串是否是另一个字符串的子串
递归是降低二叉树时间复杂度的有效方式，时间复杂度一般可以用O(n^2)降低到O(n)，缺点就是带来了O(logN)的空间复杂度，logN是非常小的复杂度，相对来说，递归解决二叉树在绝大多数情况下，是一种相对较为优的解法。
1. 翻转二叉树(输出二叉树的镜像)
- 递归方式:
/**
* 翻转二叉树（又叫：二叉树的镜像）
* @param rootNode 根节点
* @return 翻转后的树根节点（其实就是原二叉树的根节点）
*/
+ (BinaryTreeNode *)invertBinaryTree:(BinaryTreeNode *)rootNode {
if (!rootNode) {
return nil;
}
if (!rootNode.leftNode&&!rootNode.rightNode) {
return rootNode;
}
[BinaryTreeNode invertBinaryTree:rootNode.leftNode];
[BinaryTreeNode invertBinaryTree:rootNode.rightNode];
BinaryTreeNode *tempNode = rootNode.rightNode;
rootNode.rightNode = rootNode.leftNode;
rootNode.leftNode = tempNode;
return tempNode;
}
- 非递归方式翻转
算法思想：
1、根结点入队列，即放入列尾。
2、从队列中取出一个结点，即从队列头部取出一个元素。
3、将取出来的结点的左右儿子交换，然后依次放入队列尾部。
4、如果队列不为空，循环执行第2、3步。
/**
* 非递归方式翻转
*/
+ (BinaryTreeNode *)invertBinaryTreeNot:(BinaryTreeNode *)rootNode {
if (!rootNode) {
return nil;
}
if (!rootNode.leftNode&&!rootNode.rightNode) {
return rootNode;
}
NSMutableArray *queryArray = [NSMutableArray array];
[queryArray addObject:rootNode];
while (queryArray.count>0) {
BinaryTreeNode *node =queryArray.firstObject;
BinaryTreeNode *tempNode = node.rightNode;
node.rightNode = node.leftNode;
node.leftNode = tempNode;
[queryArray removeObjectAtIndex:0];
if (node.leftNode) {
[queryArray addObject:node.leftNode];
}
if (node.rightNode) {
[queryArray addObject:node.rightNode];
}
}
return rootNode;
}
2.二叉树中最远两个结点的距离
思路:递归整个树,获取每个节点的深度并比较,取得一个最大的就是最远两个节点的距离,时间复杂度 O(n).
+ (NSInteger)maxDistanceOfTree3:(BinaryTreeNode *)rootNode {
if (rootNode == nil) {
return 0;
}
int max = 0;
[self maxDistance:rootNode max:&max];
return max;
}
+ (int)maxDistance:(BinaryTreeNode *)rootNode max:(int *)max
{
if (rootNode == nil) {
return 0;
}
int leftDepth = [self maxDistance:rootNode.leftNode max:max];
int rightDepth = [self maxDistance:rootNode.rightNode max:max];
if (leftDepth + rightDepth > *max) {
*max = leftDepth + rightDepth;
}
return MAX(leftDepth, rightDepth)+1;
}
3.二叉树的深度
/**
* 二叉树的深度
* @param rootNode 二叉树根节点
* @return 二叉树的深度
*/
+ (NSInteger)depthOfTree:(BinaryTreeNode *)rootNode {
if (!rootNode) {
return 0;
}
if (!rootNode.leftNode&&!rootNode.rightNode) {
return 1;
}
NSInteger leftDepth = [BinaryTreeNode depthOfTree:rootNode.leftNode];
NSInteger rightDepth = [BinaryTreeNode depthOfTree:rootNode.rightNode];
return MAX(leftDepth, rightDepth)+1;
}
4.求二叉树中两个节点的最低公共祖先节点
求二叉树中两个节点的最低公共祖先节点
+(BOOL)hasNode:(BinaryTreeNode *)node InTree:(BinaryTreeNode *)tree
{
if (!node) {
return false;
}
else if ([node isEqual:tree])
{
return TRUE;
}
else
{
BOOL has =false;
if (tree.leftNode) {
has = [BinaryTreeNode hasNode:node InTree:tree.leftNode];
}
if (!has && tree.rightNode) {
has = [BinaryTreeNode hasNode:node InTree:tree.rightNode];
}
return has;
}
}
/*判断两个节点的最近公共祖先
求两个节点的公共祖先可以用到上面的：判断一个节点是否在一颗子树（1）如果两个节点同时在根节点的右子树中，则最近公共祖先一定在根节点的右子树中。（
(2）如果两个节点同时在根节点的左子树中，则最近公共祖先一定在根节点的左子树中。
（3）如果两个节点一个在根节点的右子树中，一个在根节点的左子树中，则最近公共祖先一定是根节点。当然，要注意的是：可能一个节点pNode1在以另一个节点pNode2为根的子树中，这时pNode2就是这两个节点的最近公共祖先了。
*/
+(BinaryTreeNode *)getNearestCommonFather:(BinaryTreeNode *)root oneNode:(BinaryTreeNode *)oneNode TwoNode:(BinaryTreeNode *)twoNode
{
if ([BinaryTreeNode hasNode:oneNode InTree:twoNode]) {
return twoNode;
}
if ([BinaryTreeNode hasNode:twoNode InTree:oneNode]) {
return oneNode;
}
BOOL oneInLeft,oneInRight,twoInLeft,twoInRight;
oneInLeft = [BinaryTreeNode hasNode:oneNode InTree:root.leftNode];
oneInRight = [BinaryTreeNode hasNode:oneNode InTree:root.rightNode];
twoInLeft = [BinaryTreeNode hasNode:twoNode InTree:root.leftNode];
twoInRight = [BinaryTreeNode hasNode:twoNode InTree:root.rightNode];
if ((oneInRight && oneInLeft)||(oneInLeft&&twoInRight)) {
return root;
}
else if (oneInLeft && twoInLeft)
{
[BinaryTreeNode getNearestCommonFather:root.leftNode oneNode:oneNode TwoNode:twoNode];
}
else if (oneInRight && twoInRight)
{
[BinaryTreeNode getNearestCommonFather:root.rightNode oneNode:oneNode TwoNode:twoNode];
}
else{
return nil;
}
return nil;
}
5.由前序遍历和中序遍历重建二叉树
更新中...
6.反转单链表
- 方案一:
思路:将单链表储存为数组，然后按照数组的索引逆序进行反转
///此方式比较浪费空间，而且需要两次遍历，效率不占优势
+(ListNode *)ReverseList1:(ListNode *)head
{
if (head == nil) {
return nil;
}
NSMutableArray *listArr = [NSMutableArray array];
while (head) {
[listArr addObject:head];
head = head.next;
}
for (NSInteger i = listArr.count-1; i>0; i--) {
ListNode *node = listArr[i];
if (i==0) {
node.next = nil;
}
else
{
node.next = listArr[i-1];
}
}
head = listArr[listArr.count-1];
return head;
}
- 方案二:
思路:定义3个变量，分别指向当前遍历到的结点、它的前一个结点及后一个结点。在遍历过程中，首先记录当前节点的后一个节点，然后将当前节点的后一个节点指向前一个节点，其次前一个节点再指向当前节点，最后再将当前节点指向最初记录的后一个节点，如此反复，直到当前节点的后一个节点为NULL时，则代表当前节点时反转后的头结点了
+(ListNode *)ReverseList2:(ListNode *)head
{
if (head == nil)
{
return nil;
}
ListNode * reverseHead = nil;
// 指针1：当前节点
ListNode * currentNode = head;
// 指针2：当前节点的前一个节点
ListNode * prevNode = nil;
while(currentNode != nil)
{
// 指针3：当前节点的后一个节点
ListNode * nextNode = currentNode.next;
if(nextNode == nil)
{
reverseHead = currentNode;
}
// 将当前节点的后一个节点指向前一个节点
currentNode.next = prevNode;
// 将前一个节点指向当前节点
prevNode = currentNode;
// 将当前节点指向后一个节点
currentNode = nextNode;
}
return reverseHead;
}
7.二分查找
也称折半查找,要求线性表的顺序存储结构,时间复杂度.O（log2n）
int binarySearch(int a[],int len,int val)
{
int start=0;
int end=len-1;
int index=-1;
while (start<=end)
{
index=start+(end-start)/2;
if (a[index]==val)
{
return index;
}else if (a[index]<val)
{
start=index+1;
}else
{
end=index-1;
}
}
return -1;
}
8.判断一个字符串是否是另一个字符串的子串
bool isSubsequence1(char* s, char* t) {
int slen=strlen(s);
int tlen=strlen(t);
int j=0;
for(int i=0;i<slen;i++){
if(s[i]==t[j]){
j++;
if(j==tlen)
break;
}
}
if(j==tlen)
return true;
else
return false;
}
