根据前序和中序创建二叉树
前序序列：1 2 3 4 5 6 - 中序序列 ：3 2 4 1 6 5，来重新构建二叉树。可以利用前序序列和中序序列中根节点的位置特性作为重建依据。图示解析过程如下：
解析：
前序数组：[1,3,7,9,5,11]
中序数组：[9,7,3,1,5,11]
根据前序数组可以知道二叉树根节点为1，那么可以将中序数组划分为两个子数组，元素1左边[9,7,3]是左子树节点数组，右边[5,11]是右子树节点数组，并且一个是左子树前序遍历，一个是右子树前序遍历。
此时前序数组划分为左右子树的前序数组：[3,7,9] , [5,11]。(这里的划分是根据前序数组左右子树划分出来的节点数，左边3个元素，右边两个元素)
递归进行数组划分
划分过程如下：
确定根节点： 1 3 5 7
划分中序数组：[9,7,3] , [5,11] [9,7] , 空 空 , [11] [9] , 空
划分前序数组：[3,7,9] , [5,11] [7,9] , 空 空 , [11] [9] , 空
得到二叉树：
1
3 5
7 11
9
@interface Node : NSObject
@property (nonatomic,strong) Node *left;
@property (nonatomic,strong) Node *right;
@property (nonatomic,assign) NSInteger value;
+(instancetype)nodeWithValue:(NSInteger)value;
@interface BinaryTree : NSObject
@property (nonatomic,strong) Node *root;
-(Node *)buildWithPreArr:(NSArray *)preArr inArr:(NSArray *)inArr;
@end
-(Node *)buildWithPreArr:(NSArray *)preArr inArr:(NSArray *)inArr
{
if (inArr.count == 0) {
return nil;
}
Node *node = [Node nodeWithValue:[preArr.firstObject integerValue]];
if (!self.root) {
self.root = node;
}
NSInteger rootIndex = 0;
while (rootIndex<inArr.count) {
if ([inArr[rootIndex] integerValue] == [preArr.firstObject integerValue])
break;
rootIndex ++;
}
node.left = [self buildWithPreArr:[preArr subarrayWithRange:NSMakeRange(1, preArr.count-1)] inArr:[inArr subarrayWithRange:NSMakeRange(0, rootIndex)]];
node.right = [self buildWithPreArr:[preArr subarrayWithRange:NSMakeRange(1+rootIndex, preArr.count-(1+rootIndex))] inArr:[inArr subarrayWithRange:NSMakeRange(rootIndex+1, inArr.count-(1+rootIndex))]];
return node;
}
-(Node *)buildWithPostArr:(NSArray *)postArr inArr:(NSArray *)inArr
{
if (inArr.count == 0) {
return nil;
}
Node *node = [Node nodeWithValue:[postArr.lastObject integerValue]];
if (!self.root) {
self.root = node;
}
NSInteger rootIndex = 0;
while (rootIndex<inArr.count) {
if ([inArr[rootIndex] integerValue] == [postArr.lastObject integerValue])
break;
rootIndex ++;
}
node.left = [self buildWithPostArr:[postArr subarrayWithRange:NSMakeRange(0, rootIndex)] inArr:[inArr subarrayWithRange:NSMakeRange(0, rootIndex)]];
node.right = [self buildWithPostArr:[postArr subarrayWithRange:NSMakeRange(rootIndex, postArr.count-(rootIndex+1))] inArr:[inArr subarrayWithRange:NSMakeRange(rootIndex+1, inArr.count-(rootIndex+1))]];
return node;
}
二叉树层序遍历获取某个index的节点（利用队列先进先出的性质）
75431539855031_.pic.jpg
-(Node *)printTree:(NSInteger)index
{
if(index<0||!self.root)return nil;
NSMutableArray *arr = [NSMutableArray array];//初始化队列Q
[arr addObject:self.root];//首先入队根节点 //-------------------------------- （Q={起点s}；标记s为已访问）
while (arr.count!=0) { //-------------------------------- while(Q非空)
//每次获取队列首个节点
Node *node = arr.firstObject; //-------------------------------- 取Q队首元素u；
if (index == 0) { //-------------------------------- if(u==目标状态){…}；
return node;
}
//首个节点出队
[arr removeObjectAtIndex:0]; //-------------------------------- 队首元素u出队；
index --;//移除节点，index减少
//如果该节点有左孩子节点，那么入队
if (node.left) { //-------------------------------- 所有与u相邻且未被访问的点进入队列，标记u为已访问；
[arr addObject:node.left];
}
//如果该节点有右孩子节点，那么入队
if (node.right) {
[arr addObject:node.right];
}
}
return nil;//层次遍历完，仍然没有找到位置，返回nil
}
二叉树层序遍历解析：
1
3 5
7 4 6 8
9
入队根节点1
--------------------------------
1
--------------------------------
进入while循环，出队根节点1，入队左右孩子节点3，5
--------------------------------
3 5
--------------------------------
节点3出队，入队3的左右孩子节点7，4；
--------------------------------
5 7 4
--------------------------------
节点5出队入队5的左右孩子节点6，8
--------------------------------
7 4 6 8
--------------------------------
节点7出队入队7的左孩子节点9
--------------------------------
4 6 8 9
--------------------------------
因为4、6、8、9没有左右孩子节点，所以直接依次出队
当队列中没有节点的时候，循环结束
扩展：如果将二叉树非叶子节点的左右孩子进行交换，那么层序遍历只需要先入队右孩子节点然后入队左孩子节点。
求二叉树的深度
二叉树的深度定义为：从根节点到叶子结点依次经过的结点形成树的一条路径,最长路径的长度为树的深度。
1）如果根节点为空，则深度为0；
2）递归思想：二叉树的深度=max（左子树的深度，右子树的深度）+ 1（加1是加上当前节点）
深度和高度区别：深度是从根节点数到它的叶节点，高度是从叶节点数到它的根节点。二叉树的深度是从根节点开始（其深度为1）自顶向下逐层累加的；而二叉树高度是从叶节点开始（其高度为1）自底向上逐层累加的。虽然树的深度和高度一样，但是具体到树的某个节点，其深度和高度是不一样的。
/**
* 二叉树的深度
*
* @param rootNode 二叉树根节点
*
* @return 二叉树的深度
*/
+ (NSInteger)depthOfTree:(BinaryTreeNode *)rootNode {
if (!rootNode) {
return 0;
}
//左子树深度
NSInteger leftDepth = [self depthOfTree:rootNode.leftNode];
//右子树深度
NSInteger rightDepth = [self depthOfTree:rootNode.rightNode];
return MAX(leftDepth, rightDepth) + 1;
}
#求二叉树的宽度
//二叉树的宽度定义为各层节点数的最大值。
+ (NSInteger)widthOfTree:(BinaryTreeNode *)rootNode {
if (!rootNode) {
return 0;
}
NSMutableArray *queueArray = [NSMutableArray array]; //数组当成队列
[queueArray addObject:rootNode]; //压入根节点
NSInteger maxWidth = 1; //最大的宽度，初始化为1（因为已经有根节点）
NSInteger curWidth = 1; //当前层的宽度，初始化为1（因为已经有根节点）
while (queueArray.count > 0) {
curWidth = queueArray.count;
//得到当前队列中的节点数后，这些节点都在同一层，分别出队并入队他们的左右子节点
for (NSInteger i=0; i<curWidth; i++) {
BinaryTreeNode *node = [queueArray firstObject];
[queueArray removeObjectAtIndex:0]; //弹出最前面的节点，仿照队列先进先出原则
//压入子节点
if (node.leftNode) {
[queueArray addObject:node.leftNode];
}
if (node.rightNode) {
[queueArray addObject:node.rightNode];
}
}
//宽度 = 当前层节点数（即当前队列中的元素个数）
maxWidth = MAX(maxWidth, queueArray.count);
}
return maxWidth;
}
解析：每次弹出当前层的节点之后，入队当前层的所有节点的左右子节点，也就是下一层的所有节点，因此每次循环结束，队列queueArray里面保存的都是下一层的所有节点，所以每次队列里面节点的个数，就是每层节点的个数，对所有层节点的个数做比较，取最大值，就是树的宽度。
二叉树的所有节点数
递归思想：二叉树所有节点数=左子树节点数+右子树节点数+1
/**
* 二叉树的所有节点数
*
* @param rootNode 根节点
*
* @return 所有节点数
*/
+ (NSInteger)numberOfNodesInTree:(BinaryTreeNode *)rootNode {
if (!rootNode) {
return 0;
}
//节点数=左子树节点数+右子树节点数+1（根节点）
return [self numberOfNodesInTree:rootNode.leftNode] + [self numberOfNodesInTree:rootNode.rightNode] + 1;
}
二叉树中某个节点到根节点的路径
既是寻路问题，又是查找节点问题。
定义一个存放路径的栈（不是队列了，但是还是用可变数组来实现的）
1）压入根节点，再从左子树中查找（递归进行的），如果未找到，再从右子树中查找，如果也未找到，则弹出根节点，再遍历栈中上一个节点。
2）如果找到，则栈中存放的节点就是路径所经过的节点。
/**
* 二叉树中某个节点到根节点的路径
*
* @param treeNode 节点
* @param rootNode 根节点
*
* @return 存放路径节点的数组
*/
+ (NSArray *)pathOfTreeNode:(Node *)treeNode inTree:(Node *)rootNode {
NSMutableArray *stackArr = [NSMutableArray array];
[self findPathTo:treeNode inTree:rootNode pathArr:stackArr];
return stackArr;
}
/**
* 查找某个节点是否在树中
*
* @param treeNode 待查找的节点
* @param rootNode 根节点
* @param path 根节点到待查找节点的路径
*
* @return YES：找到，NO：未找到
*/
+(BOOL)findPathTo:(Node *)node rootNode:(Node *)rootNode pathArr:(NSMutableArray *)stackArr
{
if (!rootNode||!node) {
return NO;
}
//找到相同节点，压入栈中，然后返回YES
if (rootNode.value == node.value) {
[stackArr addObject:rootNode];
return YES;
}
//压入根节点，进行递归
[stackArr addObject:rootNode];
//先从左子树中查找
BOOL find = [self findPathTo:node rootNode:rootNode.left pathArr:stackArr];
//未找到，再从右子树查找
if (!find) {
find = [self findPathTo:node rootNode:rootNode.right pathArr:stackArr];
}
//如果两边都没查找到，则弹出此根节点
if (!find) {
[stackArr removeLastObject];
}
return find;
}
二叉树中两个节点最近的公共父节点
首先需要明白，根节点肯定是二叉树中任意两个节点的公共父节点（不一定是最近的），因此二叉树中2个节点的最近公共父节点一定在从根节点到这个节点的路径上。因此我们可以先分别找到从根节点到这2个节点的路径，再从这两个路径中找到最近的公共父节点。
/**
* 二叉树中两个节点最近的公共父节点
*
* @param nodeA 第一个节点
* @param nodeB 第二个节点
* @param rootNode 二叉树根节点
*
* @return 最近的公共父节点
*/
+ (Node *)parentOfNode:(Node *)nodeA andNode:(Node *)nodeB inTree:(Node *)rootNode {
if (!rootNode || !nodeA || !nodeB) {
return nil;
}
if (nodeA == nodeB) {
return nodeA;
}
//从根节点到节点A的路径
NSArray *pathA = [self pathOfTreeNode:nodeA inTree:rootNode];
//从根节点到节点B的路径
NSArray *pathB = [self pathOfTreeNode:nodeB inTree:rootNode];
//其中一个节点不在树中，则没有公共父节点
if (pathA.count == 0 || pathB == 0) {
return nil;
}
//从后往前推，查找第一个出现的公共节点
for (NSInteger i = pathA.count-1; i>=0; i--) {
for (NSInteger j = pathB.count - 1; j>=0; j--) {
if ([pathA objectAtIndex:i] == [pathB objectAtIndex:j]) {
//找到
return [pathA objectAtIndex:i];
}
}
}
return nil;
}
反转二叉树
/**
* 翻转二叉树（又叫：二叉树的镜像）
*
* @param rootNode 根节点
*
* @return 翻转后的树根节点（其实就是原二叉树的根节点）
*/
+(Node *)reverseTree:(Node *)rootNode
{
if (!rootNode) {
return nil;
}
//1.反转左孩子的孩子节点
rootNode.left = [self reverseTree:rootNode.left];
//2.反转右孩子的孩子节点
rootNode.right = [self reverseTree:rootNode.right];
//3.反转左孩子和右孩子节点（这个步骤也可以放在第一步之前）
Node *node = rootNode.left;
rootNode.left = rootNode.right;
rootNode.right = node;
return rootNode;
}
二叉树中两个节点之间的路径
从查找最近公共父节点衍生出来的。
/**
* 二叉树中两个节点之间的路径
*
* @param nodeA 第一个节点
* @param nodeB 第二个节点
* @param rootNode 二叉树根节点
*
* @return 两个节点间的路径
*/
+ (NSArray *)pathFromNode:(BinaryTreeNode *)nodeA toNode:(BinaryTreeNode *)nodeB inTree:(BinaryTreeNode *)rootNode {
if (!rootNode || !nodeA || !nodeB) {
return nil;
}
NSMutableArray *path = [NSMutableArray array];
if (nodeA == nodeB) {
[path addObject:nodeA];
[path addObject:nodeB];
return path;
}
//从根节点到节点A的路径
NSArray *pathA = [self pathOfTreeNode:nodeA inTree:rootNode];
//从根节点到节点B的路径
NSArray *pathB = [self pathOfTreeNode:nodeB inTree:rootNode];
//其中一个节点不在树中，则没有路径
if (pathA.count == 0 || pathB == 0) {
return nil;
}
//从后往前推，查找第一个出现的公共节点
for (NSInteger i = pathA.count-1; i>=0; i--) {
[path addObject:[pathA objectAtIndex:i]];
for (NSInteger j = pathB.count - 1; j>=0; j--) {
//找到公共父节点，则将pathB中后面的节点压入path
if ([pathA objectAtIndex:i] == [pathB objectAtIndex:j]) {
j++; //j++是为了避开公共父节点
while (j<pathB.count) {
[path addObject:[pathB objectAtIndex:j]];
j++;
}
return path;
}
}
}
return nil;
}
二叉树两个节点之间的距离
可以从两个节点之间的路径衍生出来。
/**
* 二叉树两个节点之间的距离
*
* @param nodeA 第一个节点
* @param nodeB 第二个节点
* @param rootNode 二叉树根节点
*
* @return 两个节点间的距离（-1：表示没有找到路径）
*/
+ (NSInteger)distanceFromNode:(BinaryTreeNode *)nodeA toNode:(BinaryTreeNode *)nodeB inTree:(BinaryTreeNode *)rootNode {
if (!rootNode || !nodeA || !nodeB) {
return -1;
}
if (nodeA == nodeB) {
return 0;
}
//从根节点到节点A的路径
NSArray *pathA = [self pathOfTreeNode:nodeA inTree:rootNode];
//从根节点到节点B的路径
NSArray *pathB = [self pathOfTreeNode:nodeB inTree:rootNode];
//其中一个节点不在树中，则没有路径
if (pathA.count == 0 || pathB == 0) {
return -1;
}
//从后往前推，查找第一个出现的公共节点
for (NSInteger i = pathA.count-1; i>=0; i--) {
for (NSInteger j = pathB.count - 1; j>=0; j--) {
//找到公共父节点
if ([pathA objectAtIndex:i] == [pathB objectAtIndex:j]) {
//距离=路径节点数-1 （这里要-2，因为公共父节点重复了一次）
return (pathA.count - i) + (pathB.count - j) - 2;
}
}
}
return -1;
}
判断二叉树是否完全二叉树
完全二叉树定义为：若设二叉树的高度为 h，除第 h 层外，其它各层的结点数都达到最大个数，第 h 层有叶子结点，并且叶子结点都是从左到右依次排布。
完全二叉树必须满足 2 个条件：
1）如果某个节点的右子树不为空，则它的左子树必须不为空
2）如果某个节点的右子树为空，则排在它后面的节点必须没有孩子节点
这里还需要理解“排在它后面的节点”，回头看看层次遍历算法，我们就能知道在层次遍历时，是从上到下从左到右遍历的，先将根节点弹出队列，再压入孩子节点，因此“排在它后面的节点”有 2 种情况：
1）同层次的后面的节点
2）同层次的前面的节点的孩子节点（因为遍历前面的节点时，会弹出节点，同时将孩子节点压入队列）
通过上面的分析，我们可以设置一个标志位flag，当子树满足完全二叉树时，设置flag=YES。当flag=YES而节点又破坏了完全二叉树的条件，那么它就不是完全二叉树。
/**
* 是否完全二叉树
* 完全二叉树：若设二叉树的高度为h，除第h层外，其它各层的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布
*
* @param rootNode 根节点
*
* @return YES：是完全二叉树，NO：不是完全二叉树
*/
+ (BOOL)isCompleteBinaryTree:(BinaryTreeNode *)rootNode {
if (!rootNode) {
return NO;
}
//左子树和右子树都是空，则是完全二叉树
if (!rootNode.leftNode && !rootNode.rightNode) {
return YES;
}
//左子树是空，右子树不是空，则不是完全二叉树
if (!rootNode.leftNode && rootNode.rightNode) {
return NO;
}
//按层次遍历节点，找到满足完全二叉树的条件：
//条件1：如果某个节点的右子树不为空，则它的左子树必须不为空
//条件2：如果某个节点的右子树为空，则排在它后面的节点必须没有孩子节点
//排在该节点后面的节点有2种：1）同层次的后面的节点 2）同层次的前面的节点的孩子节点（因为遍历前面的节点的时候，会将节点从队列里pop，同时把它的孩子节点push到队列里）
NSMutableArray *queue = [NSMutableArray array];
[queue addObject:rootNode];
BOOL isComplete = NO; //是否已经满足完全二叉树
while (queue.count > 0) {
BinaryTreeNode *node = [queue firstObject];
[queue removeObjectAtIndex:0];
//左子树为空且右子树不为空，则不是完全二叉树
if (!node.leftNode && node.rightNode) {
return NO;
}
if (isComplete && (node.leftNode || node.rightNode)) {
//前面的节点已满足完全二叉树,如果还有孩子节点，则不是完全二叉树
return NO;
}
//右子树为空，则已经满足完全二叉树
if (!node.rightNode) {
isComplete = YES;
}
//压入
if (node.leftNode) {
[queue addObject:node.leftNode];
}
if (node.rightNode) {
[queue addObject:node.rightNode];
}
}
return isComplete;
}
判断二叉树是否满二叉树
满二叉树定义为：除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树
满二叉树的一个特性是：叶子数=2^(深度-1)，因此我们可以根据这个特性来判断二叉树是否是满二叉树。（也就是求出二叉树的深度和节点的总个数，然后满足公式就行了）
/**
* 是否满二叉树
* 满二叉树：除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树
*
* @param rootNode 根节点
*
* @return YES：满二叉树，NO：非满二叉树
*/
+ (BOOL)isFullBinaryTree:(BinaryTreeNode *)rootNode {
if (!rootNode) {
return NO;
}
//二叉树深度
NSInteger depth = [self depthOfTree:rootNode];
//二叉树叶子节点数
NSInteger leafNum = [self numberOfLeafsInTree:rootNode];
//满二叉树特性：叶子数=2^(深度-1)
if (leafNum == pow(2, (depth - 1))) {
return YES;
}
return NO;
}
判断二叉树是否平衡二叉树
平衡二叉树定义为：它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1 ，并且左右两个子树都是一棵平衡二叉树。平衡二叉树又叫 AVL树。
/**
* 是否平衡二叉树
* 平衡二叉树：即AVL树，它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
*
* @param rootNode 根节点
*
* @return YES：平衡二叉树，NO：非平衡二叉树
*/
+ (BOOL)isAVLBinaryTree:(BinaryTreeNode *)rootNode {
static NSInteger height;
if (!rootNode) {
height = 0;
return YES;
}
if (!rootNode.leftNode && !rootNode.rightNode) {
height = 1;
return YES;
}
BOOL isAVLLeft = [self isAVLBinaryTree:rootNode.leftNode];
NSInteger heightLeft = height;
BOOL isAVLRight = [self isAVLBinaryTree:rootNode.rightNode];
NSInteger heightRight = height;
height = MAX(heightLeft, heightRight)+1;
if (isAVLLeft && isAVLRight && ABS(heightLeft-heightRight) <= 1) {
return YES;
}
return NO;
}
链接：https://www.cnblogs.com/33debug/p/7252371.html
http://www.cnblogs.com/manji/p/4903990.html
网友评论