常用算法

1.反转二叉树

// "BinaryTreeNode.h"
#import <Foundation/Foundation.h>
@interface BinaryTreeNode : NSObject
/***  值*/
@property (nonatomic, assign) NSInteger value;
/***  左节点 */
@property (nonatomic, strong) BinaryTreeNode *leftNode;
/***  右节点 */
@property (nonatomic, strong) BinaryTreeNode *rightNode;
@end

object-c实现：

/**
* 翻转二叉树（又叫：二叉树的镜像）
*
* @param rootNode 根节点
*
* @return 翻转后的树根节点（其实就是原二叉树的根节点）
*/
+ (BinaryTreeNode *)invertBinaryTree:(BinaryTreeNode *)rootNode {
if (!rootNode) {  return nil; }
if (!rootNode.leftNode && !rootNode.rightNode) {  return rootNode; }
[self invertBinaryTree:rootNode.leftNode];
[self invertBinaryTree:rootNode.rightNode];
BinaryTreeNode *tempNode = rootNode.leftNode;
rootNode.leftNode = rootNode.rightNode;
rootNode.rightNode = tempNode;
return rootNode;
}

非递归方式：

+ (BinaryTreeNode *)invertBinaryTree:(BinaryTreeNode *)rootNode {
if (!rootNode) {  return nil; }
if (!rootNode.leftNode && !rootNode.rightNode) {  return rootNode; }
NSMutableArray *queueArray = [NSMutableArray array]; //数组当成队列
[queueArray addObject:rootNode]; //压入根节点
while (queueArray.count > 0) {
BinaryTreeNode *node = [queueArray firstObject];
[queueArray removeObjectAtIndex:0]; //弹出最前面的节点，仿照队列先进先出原则
BinaryTreeNode *pLeft = node.leftNode;
node.leftNode = node.rightNode;
node.rightNode = pLeft;
if (node.leftNode) {
[queueArray addObject:node.leftNode];
}
if (node.rightNode) {
[queueArray addObject:node.rightNode];
}
}
return rootNode;
}

---代码实现

//  ViewController.m
#import "BinaryTreeNode.h"
@interface ViewController ()

@end

@implementation ViewController

- (void)viewDidLoad {
    [super viewDidLoad];
   
    NSArray *arr = @[@4,@2,@7,@1,@3,@6,@9];
    BinaryTreeNode *node = [[self class] createTreeWithValues:arr];
    NSLog(@"%@",node);
    BinaryTreeNode *overNode = [[self class] invertBinaryTree:node];
    NSLog(@"%@",overNode);
}

+ (BinaryTreeNode *)createTreeWithValues:(NSArray *)values {
    BinaryTreeNode *root = nil;
    for (NSInteger i=0; i<values.count; i++) {
        NSInteger value = [(NSNumber *)[values objectAtIndex:i] integerValue];
        root = [[self class] addTreeNode:root value:value];
    }
    return root;
}

+ (BinaryTreeNode *)addTreeNode:(BinaryTreeNode *)treeNode value:(NSInteger)value {
    //根节点不存在，创建节点
    if (!treeNode) {
        treeNode = [BinaryTreeNode new];
        treeNode.value = value;
        NSLog(@"node:%@", @(value));
    }
    else if (value <= treeNode.value) {
        NSLog(@"to left");
        //值小于根节点，则插入到左子树
        treeNode.leftNode = [[self class] addTreeNode:treeNode.leftNode value:value];
    }
    else {
        NSLog(@"to right");
        //值大于根节点，则插入到右子树
        treeNode.rightNode = [[self class] addTreeNode:treeNode.rightNode value:value];
    }
    return treeNode;
}

+ (BinaryTreeNode *)invertBinaryTree:(BinaryTreeNode *)rootNode {
    if (!rootNode) {  return nil; }
    if (!rootNode.leftNode && !rootNode.rightNode) {  return rootNode; }
    NSMutableArray *queueArray = [NSMutableArray array]; //数组当成队列
    [queueArray addObject:rootNode]; //压入根节点
    while (queueArray.count > 0) {
        BinaryTreeNode *node = [queueArray firstObject];
        [queueArray removeObjectAtIndex:0]; //弹出最前面的节点，仿照队列先进先出原则
        BinaryTreeNode *pLeft = node.leftNode;
        node.leftNode = node.rightNode;
        node.rightNode = pLeft;
        
        if (node.leftNode) {
            [queueArray addObject:node.leftNode];
        }
        if (node.rightNode) {
            [queueArray addObject:node.rightNode];
        }
        
    }
  
    return rootNode;
}
@end