/
ViewController.m
86 lines (72 loc) · 2.46 KB
/
ViewController.m
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
//
// ViewController.m
// ttt
//
// Created by DeterTao on 16/4/7.
// Copyright © 2016年 DeterTao. All rights reserved.
//
#import "ViewController.h"
#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;
}
- (void)didReceiveMemoryWarning {
[super didReceiveMemoryWarning];
// Dispose of any resources that can be recreated.
}
@end