去年二叉樹算法的事情鬧的沸沸揚(yáng)揚(yáng)，起因是Homebrew 的作者 @Max Howell 在 twitter 上發(fā)表了如下一內(nèi)容：
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.
事情大概是說球凰，Max Howell 去 Google 面試，面試官說：雖然在 Google 有 90% 的工程師用你寫的 Homebrew杨名，但是你居然不能在白板上寫出翻轉(zhuǎn)二叉樹的代碼，所以滾蛋吧猖毫。
雖然我不是科班出身台谍，但是因?yàn)楣ぷ髟颍惴ㄒ灿兴娅C吁断，雖然懂的不多趁蕊，但是Max大神居然答不出二叉樹的問題，作為小透明還是應(yīng)該復(fù)習(xí)下二叉樹的相關(guān)基礎(chǔ)知識的仔役。
什么是二叉樹
在計(jì)算機(jī)科學(xué)中掷伙，二叉樹是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹的樹結(jié)構(gòu)。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）又兵。二叉樹常被用于實(shí)現(xiàn)二叉查找樹和二叉堆任柜。
——百度百科
二叉樹的子樹有左右之分，并且次序不能任意顛倒沛厨。二叉樹是遞歸定義的宙地，所以一般二叉樹的相關(guān)題目也都可以使用遞歸的思想來解決，當(dāng)然也有一些可以使用非遞歸的思想解決.
什么是二叉排序樹逆皮？
二叉排序樹又叫二叉查找樹或者二叉搜索樹宅粥，它首先是一個(gè)二叉樹，而且必須滿足下面的條件：
1）若左子樹不空电谣，則左子樹上所有結(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值秽梅；
2）若右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值
3）左辰企、右子樹也分別為二叉排序樹
4）沒有鍵值相等的節(jié)點(diǎn)
以上概念來自網(wǎng)上风纠，下面上代碼
可以看我封裝的二叉樹分類，會比文章里稍微清晰些
Masazumi柒的github——二叉樹學(xué)習(xí)
二叉樹節(jié)點(diǎn)定義
采用單項(xiàng)鏈表的形式牢贸，只從根節(jié)點(diǎn)指向孩子節(jié)點(diǎn)，不保存父節(jié)點(diǎn)镐捧。
將二叉樹節(jié)點(diǎn)設(shè)為model潜索，以下為.h
/**
* 二叉樹節(jié)點(diǎn)
*/
@interface BinaryTreeNode : NSObject
/**
* 值
*/
@property (nonatomic, assign) NSInteger value;
/**
* 左節(jié)點(diǎn)
*/
@property (nonatomic, strong) BinaryTreeNode *leftNode;
/**
* 右節(jié)點(diǎn)
*/
@property (nonatomic, strong) BinaryTreeNode *rightNode;
創(chuàng)建二叉排序樹
二叉樹中左右節(jié)點(diǎn)值本身沒有大小之分臭增，所以如果要創(chuàng)建二叉樹，就需要考慮如何處理某個(gè)節(jié)點(diǎn)是左節(jié)點(diǎn)還是右節(jié)點(diǎn)竹习，如何終止某個(gè)子樹而切換到另一個(gè)子樹誊抛。 因此我選擇了二叉排序樹，二叉排序樹中對于左右節(jié)點(diǎn)有明確的要求整陌，程序可以自動根據(jù)鍵值大小自動選擇是左節(jié)點(diǎn)還是右節(jié)點(diǎn)拗窃。（以下默認(rèn)先為.h文件中的方法聲明，后為.m的方法實(shí)現(xiàn))
/**
* 創(chuàng)建二叉排序樹
* 二叉排序樹：左節(jié)點(diǎn)值全部小于根節(jié)點(diǎn)值泌辫，右節(jié)點(diǎn)值全部大于根節(jié)點(diǎn)值
*
* @param values 數(shù)組
*
* @return 二叉樹根節(jié)點(diǎn)
*/
+ (TyBinaryTreeNode *)createTreeWithValues:(NSArray *)values;
/**
* 向二叉排序樹節(jié)點(diǎn)添加一個(gè)節(jié)點(diǎn)
*
* @param treeNode 根節(jié)點(diǎn)
* @param value 值
*
* @return 根節(jié)點(diǎn)
*/
+ (TyBinaryTreeNode *)addTreeNode:(TyBinaryTreeNode *)treeNode value:(NSInteger)value;
#pragma mark - 創(chuàng)建二叉排序樹
+ (TyBinaryTreeNode *)createTreeWithValues:(NSArray *)values {
TyBinaryTreeNode *root = nil;
for (NSInteger i=0; i<values.count; i++) {
NSInteger value = [(NSNumber *)[values objectAtIndex:i] integerValue];
root = [TyBinaryTree addTreeNode:root value:value];
}
return root;
}
#pragma mark - 向二叉排序樹節(jié)點(diǎn)添加一個(gè)節(jié)點(diǎn)
+ (TyBinaryTreeNode *)addTreeNode:(TyBinaryTreeNode *)treeNode value:(NSInteger)value {
//根節(jié)點(diǎn)不存在随夸，創(chuàng)建節(jié)點(diǎn)
if (!treeNode) {
treeNode = [TyBinaryTreeNode new];
treeNode.value = value;
NSLog(@"node:%@", @(value));
}
else if (value <= treeNode.value) {
NSLog(@"to left");
//值小于根節(jié)點(diǎn)，則插入到左子樹
treeNode.leftNode = [TyBinaryTree addTreeNode:treeNode.leftNode value:value];
}
else {
NSLog(@"to right");
//值大于根節(jié)點(diǎn)震放，則插入到右子樹
treeNode.rightNode = [TyBinaryTree addTreeNode:treeNode.rightNode value:value];
}
return treeNode;
}
二叉樹中某個(gè)位置的節(jié)點(diǎn)
類似索引操作宾毒，按層次遍歷，位置從0開始算殿遂。
/**
* 二叉樹中某個(gè)位置的節(jié)點(diǎn)（按層次遍歷）
*
* @param index 按層次遍歷樹時(shí)的位置(從0開始算)
* @param rootNode 樹根節(jié)點(diǎn)
*
* @return 節(jié)點(diǎn)
*/
+ (TyBinaryTreeNode *)treeNodeAtIndex:(NSInteger)index inTree:(TyBinaryTreeNode *)rootNode;
#pragma mark - 二叉樹中某個(gè)位置的節(jié)點(diǎn)（按層次遍歷）
+ (TyBinaryTreeNode *)treeNodeAtIndex:(NSInteger)index inTree:(TyBinaryTreeNode *)rootNode {
//按層次遍歷
if (!rootNode || index < 0) {
return nil;
}
NSMutableArray *queueArray = [NSMutableArray array]; //數(shù)組當(dāng)成隊(duì)列
[queueArray addObject:rootNode]; //壓入根節(jié)點(diǎn)
while (queueArray.count > 0) {
TyBinaryTreeNode *node = [queueArray firstObject];
if (index == 0) {
return node;
}
[queueArray removeObjectAtIndex:0]; //彈出最前面的節(jié)點(diǎn)诈铛，仿照隊(duì)列先進(jìn)先出原則
index--; //移除節(jié)點(diǎn)，index減少
if (node.leftNode) {
[queueArray addObject:node.leftNode]; //壓入左節(jié)點(diǎn)
}
if (node.rightNode) {
[queueArray addObject:node.rightNode]; //壓入右節(jié)點(diǎn)
}
}
//層次遍歷完墨礁，仍然沒有找到位置幢竹，返回nil
return nil;
}
先序遍歷
先訪問根，再遍歷左子樹恩静，再遍歷右子樹焕毫。典型的遞歸思想。
/**
* 先序遍歷
* 先訪問根蜕企，再遍歷左子樹咬荷，再遍歷右子樹
*
* @param rootNode 根節(jié)點(diǎn)
* @param handler 訪問節(jié)點(diǎn)處理函數(shù)
*/
+ (void)preOrderTraverseTree:(TyBinaryTreeNode *)rootNode handler:(void(^)(TyBinaryTreeNode *treeNode))handler;
#pragma mark - 先序遍歷
+ (void)preOrderTraverseTree:(TyBinaryTreeNode *)rootNode handler:(void(^)(TyBinaryTreeNode *treeNode))handler {
if (rootNode) {
if (handler) {
handler(rootNode);
}
[self preOrderTraverseTree:rootNode.leftNode handler:handler];
[self preOrderTraverseTree:rootNode.rightNode handler:handler];
}
}
/* 調(diào)用方法
NSMutableArray *orderArray = [NSMutableArray array];
[TyBinaryTree preOrderTraverseTree:root handler:^(BinaryTreeNode *treeNode) {
[orderArray addObject:@(treeNode.value)];
}];
*/
中序遍歷
先遍歷左子樹，再訪問根轻掩，再遍歷右子樹幸乒。
對于二叉排序樹來說，中序遍歷得到的序列是一個(gè)從小到大排序好的序列唇牧。
/**
* 中序遍歷
* 先遍歷左子樹罕扎，再訪問根，再遍歷右子樹
*
* @param rootNode 根節(jié)點(diǎn)
* @param handler 訪問節(jié)點(diǎn)處理函數(shù)
*/
+ (void)inOrderTraverseTree:(TyBinaryTreeNode *)rootNode handler:(void(^)(TyBinaryTreeNode *treeNode))handler;
#pragma mark - 中序遍歷
+ (void)inOrderTraverseTree:(TyBinaryTreeNode *)rootNode handler:(void(^)(TyBinaryTreeNode *treeNode))handler {
if (rootNode) {
[self inOrderTraverseTree:rootNode.leftNode handler:handler];
if (handler) {
handler(rootNode);
}
[self inOrderTraverseTree:rootNode.rightNode handler:handler];
}
}
后序遍歷
先遍歷左子樹丐重，再遍歷右子樹腔召，再訪問根
/**
* 后序遍歷
* 先遍歷左子樹，再遍歷右子樹扮惦，再訪問根
*
* @param rootNode 根節(jié)點(diǎn)
* @param handler 訪問節(jié)點(diǎn)處理函數(shù)
*/
+ (void)postOrderTraverseTree:(TyBinaryTreeNode *)rootNode handler:(void(^)(TyBinaryTreeNode *treeNode))handler;
#pragma mark - 后序遍歷
+ (void)postOrderTraverseTree:(TyBinaryTreeNode *)rootNode handler:(void(^)(TyBinaryTreeNode *treeNode))handler {
if (rootNode) {
[self postOrderTraverseTree:rootNode.leftNode handler:handler];
[self postOrderTraverseTree:rootNode.rightNode handler:handler];
if (handler) {
handler(rootNode);
}
}
}
層次遍歷
按照從上到下臀蛛、從左到右的次序進(jìn)行遍歷。先遍歷完一層，再遍歷下一層浊仆，因此又叫廣度優(yōu)先遍歷客峭。需要用到隊(duì)列，在OC里可以用可變數(shù)組來實(shí)現(xiàn)抡柿。
/**
* 層次遍歷（廣度優(yōu)先）
*
* @param rootNode 二叉樹根節(jié)點(diǎn)
* @param handler 訪問節(jié)點(diǎn)處理函數(shù)
*/
+ (void)levelTraverseTree:(TyBinaryTreeNode *)rootNode handler:(void(^)(TyBinaryTreeNode *treeNode))handler;
#pragma mark - 層次遍歷（廣度優(yōu)先）
+ (void)levelTraverseTree:(TyBinaryTreeNode *)rootNode handler:(void(^)(TyBinaryTreeNode *treeNode))handler {
if (!rootNode) {
return;
}
NSMutableArray *queueArray = [NSMutableArray array]; //數(shù)組當(dāng)成隊(duì)列
[queueArray addObject:rootNode]; //壓入根節(jié)點(diǎn)
while (queueArray.count > 0) {
TyBinaryTreeNode *node = [queueArray firstObject];
if (handler) {
handler(node);
}
[queueArray removeObjectAtIndex:0]; //彈出最前面的節(jié)點(diǎn)舔琅，仿照隊(duì)列先進(jìn)先出原則
if (node.leftNode) {
[queueArray addObject:node.leftNode]; //壓入左節(jié)點(diǎn)
}
if (node.rightNode) {
[queueArray addObject:node.rightNode]; //壓入右節(jié)點(diǎn)
}
}
}
二叉樹的深度
二叉樹的深度定義為：從根節(jié)點(diǎn)到葉子結(jié)點(diǎn)依次經(jīng)過的結(jié)點(diǎn)形成樹的一條路徑,最長路徑的長度為樹的深度。
1）如果根節(jié)點(diǎn)為空洲劣，則深度為0备蚓；
2）如果左右節(jié)點(diǎn)都是空，則深度為1囱稽；
3）遞歸思想：二叉樹的深度=max（左子樹的深度郊尝，右子樹的深度）+ 1
/**
* 二叉樹的深度
*
* @param rootNode 二叉樹根節(jié)點(diǎn)
*
* @return 二叉樹的深度
*/
+ (NSInteger)depthOfTree:(TyBinaryTreeNode *)rootNode;
#pragma mark - 二叉樹的深度
+ (NSInteger)depthOfTree:(TyBinaryTreeNode *)rootNode {
if (!rootNode) {
return 0;
}
if (!rootNode.leftNode && !rootNode.rightNode) {
return 1;
}
//左子樹深度
NSInteger leftDepth = [self depthOfTree:rootNode.leftNode];
//右子樹深度
NSInteger rightDepth = [self depthOfTree:rootNode.rightNode];
return MAX(leftDepth, rightDepth) + 1;
}
二叉樹的寬度
二叉樹的寬度定義為各層節(jié)點(diǎn)數(shù)的最大值。
/**
* 二叉樹的寬度
*
* @param rootNode 二叉樹根節(jié)點(diǎn)
*
* @return 二叉樹寬度
*/
+ (NSInteger)widthOfTree:(TyBinaryTreeNode *)rootNode;
#pragma mark - 二叉樹的寬度
+ (NSInteger)widthOfTree:(TyBinaryTreeNode *)rootNode {
if (!rootNode) {
return 0;
}
NSMutableArray *queueArray = [NSMutableArray array]; //數(shù)組當(dāng)成隊(duì)列
[queueArray addObject:rootNode]; //壓入根節(jié)點(diǎn)
NSInteger maxWidth = 1; //最大的寬度粗悯，初始化為1（因?yàn)橐呀?jīng)有根節(jié)點(diǎn)）
NSInteger curWidth = 0; //當(dāng)前層的寬度
while (queueArray.count > 0) {
curWidth = queueArray.count;
//依次彈出當(dāng)前層的節(jié)點(diǎn)
for (NSInteger i=0; i<curWidth; i++) {
TyBinaryTreeNode *node = [queueArray firstObject];
[queueArray removeObjectAtIndex:0]; //彈出最前面的節(jié)點(diǎn)虚循，仿照隊(duì)列先進(jìn)先出原則
//壓入子節(jié)點(diǎn)
if (node.leftNode) {
[queueArray addObject:node.leftNode];
}
if (node.rightNode) {
[queueArray addObject:node.rightNode];
}
}
//寬度 = 當(dāng)前層節(jié)點(diǎn)數(shù)
maxWidth = MAX(maxWidth, queueArray.count);
}
return maxWidth;
}
二叉樹的所有節(jié)點(diǎn)數(shù)
遞歸思想：二叉樹所有節(jié)點(diǎn)數(shù)=左子樹節(jié)點(diǎn)數(shù)+右子樹節(jié)點(diǎn)數(shù)+1
/**
* 二叉樹的所有節(jié)點(diǎn)數(shù)
*
* @param rootNode 根節(jié)點(diǎn)
*
* @return 所有節(jié)點(diǎn)數(shù)
*/
+ (NSInteger)numberOfNodesInTree:(TyBinaryTreeNode *)rootNode;
#pragma mark - 二叉樹的所有節(jié)點(diǎn)數(shù)
+ (NSInteger)numberOfNodesInTree:(TyBinaryTreeNode *)rootNode {
if (!rootNode) {
return 0;
}
//節(jié)點(diǎn)數(shù)=左子樹節(jié)點(diǎn)數(shù)+右子樹節(jié)點(diǎn)數(shù)+1（根節(jié)點(diǎn)）
return [self numberOfNodesInTree:rootNode.leftNode] + [self numberOfNodesInTree:rootNode.rightNode] + 1;
}
二叉樹某層中的節(jié)點(diǎn)數(shù)
1）根節(jié)點(diǎn)為空，則節(jié)點(diǎn)數(shù)為0样傍；
2）層為1横缔，則節(jié)點(diǎn)數(shù)為1（即根節(jié)點(diǎn)）
3）遞歸思想：二叉樹第k層節(jié)點(diǎn)數(shù)=左子樹第k-1層節(jié)點(diǎn)數(shù)+右子樹第k-1層節(jié)點(diǎn)數(shù)
/**
* 二叉樹某層中的節(jié)點(diǎn)數(shù)
*
* @param level 層
* @param rootNode 根節(jié)點(diǎn)
*
* @return 層中的節(jié)點(diǎn)數(shù)
*/
+ (NSInteger)numberOfNodesOnLevel:(NSInteger)level inTree:(TyBinaryTreeNode *)rootNode;
#pragma mark - 二叉樹某層中的節(jié)點(diǎn)數(shù)
+ (NSInteger)numberOfNodesOnLevel:(NSInteger)level inTree:(TyBinaryTreeNode *)rootNode {
if (!rootNode || level < 1) { //根節(jié)點(diǎn)不存在或者level<0
return 0;
}
if (level == 1) { //level=1，返回1（根節(jié)點(diǎn)）
return 1;
}
//遞歸：level層節(jié)點(diǎn)數(shù) = 左子樹level-1層節(jié)點(diǎn)數(shù)+右子樹level-1層節(jié)點(diǎn)數(shù)
return [self numberOfNodesOnLevel:level-1 inTree:rootNode.leftNode] + [self numberOfNodesOnLevel:level-1 inTree:rootNode.rightNode];
}
二叉樹葉子節(jié)點(diǎn)數(shù)
葉子節(jié)點(diǎn)衫哥，又叫終端節(jié)點(diǎn)茎刚，是左右子樹都是空的節(jié)點(diǎn)。
/**
* 二叉樹葉子節(jié)點(diǎn)數(shù)
*
* @param rootNode 根節(jié)點(diǎn)
*
* @return 葉子節(jié)點(diǎn)數(shù)
*/
+ (NSInteger)numberOfLeafsInTree:(TyBinaryTreeNode *)rootNode;
#pragma mark - 二叉樹葉子節(jié)點(diǎn)數(shù)
+ (NSInteger)numberOfLeafsInTree:(TyBinaryTreeNode *)rootNode {
if (!rootNode) {
return 0;
}
//左子樹和右子樹都是空撤逢，說明是葉子節(jié)點(diǎn)
if (!rootNode.leftNode && !rootNode.rightNode) {
return 1;
}
//遞歸：葉子數(shù) = 左子樹葉子數(shù) + 右子樹葉子數(shù)
return [self numberOfLeafsInTree:rootNode.leftNode] + [self numberOfLeafsInTree:rootNode.rightNode];
}
二叉樹最大距離（二叉樹的直徑）
二叉樹中任意兩個(gè)節(jié)點(diǎn)都有且僅有一條路徑膛锭，這個(gè)路徑的長度叫這兩個(gè)節(jié)點(diǎn)的距離。二叉樹中所有節(jié)點(diǎn)之間的距離的最大值就是二叉樹的直徑蚊荣。
有一種解法初狰，把這個(gè)最大距離劃分了3種情況：
1）這2個(gè)節(jié)點(diǎn)分別在根節(jié)點(diǎn)的左子樹和右子樹上，他們之間的路徑肯定經(jīng)過根節(jié)點(diǎn)互例，而且他們肯定是根節(jié)點(diǎn)左右子樹上最遠(yuǎn)的葉子節(jié)點(diǎn)（他們到根節(jié)點(diǎn)的距離=左右子樹的深度）奢入。
2）這2個(gè)節(jié)點(diǎn)都在左子樹上
3）這2個(gè)節(jié)點(diǎn)都在右子樹上
綜上，只要取這3種情況中的最大值媳叨，就是二叉樹的直徑腥光。
/**
* 二叉樹最大距離（直徑）
*
* @param rootNode 根節(jié)點(diǎn)
*
* @return 最大距離
*/
+ (NSInteger)maxDistanceOfTree:(TyBinaryTreeNode *)rootNode;
//#pragma mark - 二叉樹最大距離（直徑）
//+ (NSInteger)maxDistanceOfTree:(TyBinaryTreeNode *)rootNode {
// if (!rootNode) {
// return 0;
// }
// // 方案一：（遞歸次數(shù)較多，效率較低）
// //分3種情況：
// //1糊秆、最遠(yuǎn)距離經(jīng)過根節(jié)點(diǎn)：距離 = 左子樹深度 + 右子樹深度
// NSInteger distance = [self depthOfTree:rootNode.leftNode] + [self depthOfTree:rootNode.rightNode];
// //2武福、最遠(yuǎn)距離在根節(jié)點(diǎn)左子樹上，即計(jì)算左子樹最遠(yuǎn)距離
// NSInteger disLeft = [self maxDistanceOfTree:rootNode.leftNode];
// //3痘番、最遠(yuǎn)距離在根節(jié)點(diǎn)右子樹上捉片，即計(jì)算右子樹最遠(yuǎn)距離
// NSInteger disRight = [self maxDistanceOfTree:rootNode.rightNode];
//
// return MAX(MAX(disLeft, disRight), distance);
//}
#pragma mark - 二叉樹最大距離（直徑）
+ (NSInteger)maxDistanceOfTree:(TyBinaryTreeNode *)rootNode {
if (!rootNode) {
return 0;
}
// 方案2：將計(jì)算節(jié)點(diǎn)深度和最大距離放到一次遞歸中計(jì)算，方案一是分別單獨(dú)遞歸計(jì)算深度和最遠(yuǎn)距離
TyTreeNodeProperty *p = [self propertyOfTreeNode:rootNode];
return p.distance;
}
#pragma mark 計(jì)算樹節(jié)點(diǎn)的最大深度和最大距離
+ (TyTreeNodeProperty *)propertyOfTreeNode:(TyBinaryTreeNode *)rootNode {
if (!rootNode) {
return nil;
}
TyTreeNodeProperty *left = [self propertyOfTreeNode:rootNode.leftNode];
TyTreeNodeProperty *right = [self propertyOfTreeNode:rootNode.rightNode];
TyTreeNodeProperty *p = [TyTreeNodeProperty new];
//節(jié)點(diǎn)的深度depth = 左子樹深度、右子樹深度中最大值+1（+1是因?yàn)楦?jié)點(diǎn)占了1個(gè)depth）
p.depth = MAX(left.depth, right.depth) + 1;
//最遠(yuǎn)距離 = 左子樹最遠(yuǎn)距離界睁、右子樹最遠(yuǎn)距離和橫跨左右子樹最遠(yuǎn)距離中最大值
p.distance = MAX(MAX(left.distance, right.distance), left.depth+right.depth);
return p;
}
二叉樹中某個(gè)節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑
既是尋路問題觉增，又是查找節(jié)點(diǎn)問題兵拢。
定義一個(gè)存放路徑的棧（不是隊(duì)列了翻斟，但是還是用可變數(shù)組來實(shí)現(xiàn)的）
1）壓入根節(jié)點(diǎn)，再從左子樹中查找（遞歸進(jìn)行的）说铃，如果未找到访惜，再從右子樹中查找，如果也未找到腻扇，則彈出根節(jié)點(diǎn)债热，再遍歷棧中上一個(gè)節(jié)點(diǎn)。
2）如果找到幼苛，則棧中存放的節(jié)點(diǎn)就是路徑所經(jīng)過的節(jié)點(diǎn)窒篱。
/**
* 二叉樹中某個(gè)節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑
*
* @param treeNode 節(jié)點(diǎn)
* @param rootNode 根節(jié)點(diǎn)
*
* @return 存放路徑節(jié)點(diǎn)的數(shù)組
*/
+ (NSArray *)pathOfTreeNode:(TyBinaryTreeNode *)treeNode inTree:(TyBinaryTreeNode *)rootNode;
#pragma mark - 二叉樹中某個(gè)節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑
+ (NSArray *)pathOfTreeNode:(TyBinaryTreeNode *)treeNode inTree:(TyBinaryTreeNode *)rootNode {
NSMutableArray *pathArray = [NSMutableArray array];
[self isFoundTreeNode:treeNode inTree:rootNode routePath:pathArray];
return pathArray;
}
#pragma mark 查找某個(gè)節(jié)點(diǎn)是否在樹中
+ (BOOL)isFoundTreeNode:(TyBinaryTreeNode *)treeNode inTree:(TyBinaryTreeNode *)rootNode routePath:(NSMutableArray *)path {
if (!rootNode || !treeNode) {
return NO;
}
//找到節(jié)點(diǎn)
if (rootNode == treeNode) {
[path addObject:rootNode];
return YES;
}
//壓入根節(jié)點(diǎn)，進(jìn)行遞歸
[path addObject:rootNode];
//先從左子樹中查找
BOOL find = [self isFoundTreeNode:treeNode inTree:rootNode.leftNode routePath:path];
//未找到舶沿，再從右子樹查找
if (!find) {
find = [self isFoundTreeNode:treeNode inTree:rootNode.rightNode routePath:path];
}
//如果2邊都沒查找到墙杯，則彈出此根節(jié)點(diǎn)
if (!find) {
[path removeLastObject];
}
return find;
}
二叉樹中兩個(gè)節(jié)點(diǎn)最近的公共父節(jié)點(diǎn)
首先需要明白，根節(jié)點(diǎn)肯定是二叉樹中任意兩個(gè)節(jié)點(diǎn)的公共父節(jié)點(diǎn)（不一定是最近的）括荡，因此二叉樹中2個(gè)節(jié)點(diǎn)的最近公共父節(jié)點(diǎn)一定在從根節(jié)點(diǎn)到這個(gè)節(jié)點(diǎn)的路徑上高镐。因此我們可以先分別找到從根節(jié)點(diǎn)到這2個(gè)節(jié)點(diǎn)的路徑，再從這兩個(gè)路徑中找到最近的公共父節(jié)點(diǎn)畸冲。
/**
* 二叉樹中兩個(gè)節(jié)點(diǎn)最近的公共父節(jié)點(diǎn)
*
* @param nodeA 第一個(gè)節(jié)點(diǎn)
* @param nodeB 第二個(gè)節(jié)點(diǎn)
* @param rootNode 二叉樹根節(jié)點(diǎn)
*
* @return 最近的公共父節(jié)點(diǎn)
*/
+ (TyBinaryTreeNode *)parentOfNode:(TyBinaryTreeNode *)nodeA andNode:(TyBinaryTreeNode *)nodeB inTree:(TyBinaryTreeNode *)rootNode;
#pragma mark - 二叉樹中兩個(gè)節(jié)點(diǎn)最近的公共父節(jié)點(diǎn)
+ (TyBinaryTreeNode *)parentOfNode:(TyBinaryTreeNode *)nodeA andNode:(TyBinaryTreeNode *)nodeB inTree:(TyBinaryTreeNode *)rootNode {
if (!rootNode || !nodeA || !nodeB) {
return nil;
}
if (nodeA == nodeB) {
return nodeA;
}
//從根節(jié)點(diǎn)到節(jié)點(diǎn)A的路徑
NSArray *pathA = [self pathOfTreeNode:nodeA inTree:rootNode];
//從根節(jié)點(diǎn)到節(jié)點(diǎn)B的路徑
NSArray *pathB = [self pathOfTreeNode:nodeB inTree:rootNode];
//其中一個(gè)節(jié)點(diǎn)不在樹中嫉髓，則沒有公共父節(jié)點(diǎn)
if (pathA.count == 0 || pathB == 0) {
return nil;
}
//從后往前推，查找第一個(gè)出現(xiàn)的公共節(jié)點(diǎn)
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;
}
二叉樹中兩個(gè)節(jié)點(diǎn)之間的路徑
從查找最近公共父節(jié)點(diǎn)衍生出來的邑闲。
/**
* 二叉樹中兩個(gè)節(jié)點(diǎn)之間的路徑
*
* @param nodeA 第一個(gè)節(jié)點(diǎn)
* @param nodeB 第二個(gè)節(jié)點(diǎn)
* @param rootNode 二叉樹根節(jié)點(diǎn)
*
* @return 兩個(gè)節(jié)點(diǎn)間的路徑
*/
+ (NSArray *)pathFromNode:(TyBinaryTreeNode *)nodeA toNode:(TyBinaryTreeNode *)nodeB inTree:(TyBinaryTreeNode *)rootNode;
#pragma mark - 二叉樹中兩個(gè)節(jié)點(diǎn)之間的路徑
+ (NSArray *)pathFromNode:(TyBinaryTreeNode *)nodeA toNode:(TyBinaryTreeNode *)nodeB inTree:(TyBinaryTreeNode *)rootNode {
if (!rootNode || !nodeA || !nodeB) {
return nil;
}
NSMutableArray *path = [NSMutableArray array];
if (nodeA == nodeB) {
[path addObject:nodeA];
[path addObject:nodeB];
return path;
}
//從根節(jié)點(diǎn)到節(jié)點(diǎn)A的路徑
NSArray *pathA = [self pathOfTreeNode:nodeA inTree:rootNode];
//從根節(jié)點(diǎn)到節(jié)點(diǎn)B的路徑
NSArray *pathB = [self pathOfTreeNode:nodeB inTree:rootNode];
//其中一個(gè)節(jié)點(diǎn)不在樹中算行，則沒有路徑
if (pathA.count == 0 || pathB == 0) {
return nil;
}
//從后往前推，查找第一個(gè)出現(xiàn)的公共節(jié)點(diǎn)
for (NSInteger i = pathA.count-1; i>=0; i--) {
[path addObject:[pathA objectAtIndex:i]];
for (NSInteger j = pathB.count - 1; j>=0; j--) {
//找到公共父節(jié)點(diǎn)苫耸，則將pathB中后面的節(jié)點(diǎn)壓入path
if ([pathA objectAtIndex:i] == [pathB objectAtIndex:j]) {
j++; //j++是為了避開公共父節(jié)點(diǎn)
while (j<pathB.count) {
[path addObject:[pathB objectAtIndex:j]];
j++;
}
return path;
}
}
}
return nil;
}
二叉樹兩個(gè)節(jié)點(diǎn)之間的距離
可以從兩個(gè)節(jié)點(diǎn)之間的路徑衍生出來州邢。
/**
* 二叉樹兩個(gè)節(jié)點(diǎn)之間的距離
*
* @param nodeA 第一個(gè)節(jié)點(diǎn)
* @param nodeB 第二個(gè)節(jié)點(diǎn)
* @param rootNode 二叉樹根節(jié)點(diǎn)
*
* @return 兩個(gè)節(jié)點(diǎn)間的距離（-1：表示沒有找到路徑）
*/
+ (NSInteger)distanceFromNode:(TyBinaryTreeNode *)nodeA toNode:(TyBinaryTreeNode *)nodeB inTree:(TyBinaryTreeNode *)rootNode;
#pragma mark - 二叉樹兩個(gè)節(jié)點(diǎn)之間的距離
+ (NSInteger)distanceFromNode:(TyBinaryTreeNode *)nodeA toNode:(TyBinaryTreeNode *)nodeB inTree:(TyBinaryTreeNode *)rootNode {
if (!rootNode || !nodeA || !nodeB) {
return -1;
}
if (nodeA == nodeB) {
return 0;
}
//從根節(jié)點(diǎn)到節(jié)點(diǎn)A的路徑
NSArray *pathA = [self pathOfTreeNode:nodeA inTree:rootNode];
//從根節(jié)點(diǎn)到節(jié)點(diǎn)B的路徑
NSArray *pathB = [self pathOfTreeNode:nodeB inTree:rootNode];
//其中一個(gè)節(jié)點(diǎn)不在樹中，則沒有路徑
if (pathA.count == 0 || pathB == 0) {
return -1;
}
//從后往前推鲸阔，查找第一個(gè)出現(xiàn)的公共節(jié)點(diǎn)
for (NSInteger i = pathA.count-1; i>=0; i--) {
for (NSInteger j = pathB.count - 1; j>=0; j--) {
//找到公共父節(jié)點(diǎn)
if ([pathA objectAtIndex:i] == [pathB objectAtIndex:j]) {
//距離=路徑節(jié)點(diǎn)數(shù)-1 （這里要-2偷霉，因?yàn)楣哺腹?jié)點(diǎn)重復(fù)了一次）
return (pathA.count - i) + (pathB.count - j) - 2;
}
}
}
return -1;
}
翻轉(zhuǎn)二叉樹
你會翻轉(zhuǎn)二叉樹嗎？如果不會褐筛，那對不起类少，我們不會錄用你！
翻轉(zhuǎn)二叉樹渔扎，又叫求二叉樹的鏡像硫狞，就是把二叉樹的左右子樹對調(diào)（當(dāng)然是遞歸的）
/**
* 翻轉(zhuǎn)二叉樹（又叫：二叉樹的鏡像）
*
* @param rootNode 根節(jié)點(diǎn)
*
* @return 翻轉(zhuǎn)后的樹根節(jié)點(diǎn)（其實(shí)就是原二叉樹的根節(jié)點(diǎn)）
*/
+ (TyBinaryTreeNode *)invertBinaryTree:(TyBinaryTreeNode *)rootNode;
#pragma mark - 翻轉(zhuǎn)二叉樹（又叫：二叉樹的鏡像）
+ (TyBinaryTreeNode *)invertBinaryTree:(TyBinaryTreeNode *)rootNode {
if (!rootNode) {
return nil;
}
if (!rootNode.leftNode && !rootNode.rightNode) {
return rootNode;
}
[self invertBinaryTree:rootNode.leftNode];
[self invertBinaryTree:rootNode.rightNode];
TyBinaryTreeNode *tempNode = rootNode.leftNode;
rootNode.leftNode = rootNode.rightNode;
rootNode.rightNode = tempNode;
return rootNode;
}
判斷二叉樹是否完全二叉樹
完全二叉樹定義為：若設(shè)二叉樹的高度為h，除第h層外，其它各層的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)残吩，第h層有葉子結(jié)點(diǎn)财忽，并且葉子結(jié)點(diǎn)都是從左到右依次排布。
完全二叉樹必須滿足2個(gè)條件：
1）如果某個(gè)節(jié)點(diǎn)的右子樹不為空泣侮，則它的左子樹必須不為空
2）如果某個(gè)節(jié)點(diǎn)的右子樹為空即彪，則排在它后面的節(jié)點(diǎn)必須沒有孩子節(jié)點(diǎn)
這里還需要理解“排在它后面的節(jié)點(diǎn)”，回頭看看層次遍歷算法活尊，我們就能知道在層次遍歷時(shí)隶校，是從上到下從左到右遍歷的，先將根節(jié)點(diǎn)彈出隊(duì)列蛹锰，再壓入孩子節(jié)點(diǎn)深胳，因此“排在它后面的節(jié)點(diǎn)”有2種情況：
1）同層次的后面的節(jié)點(diǎn)
2）同層次的前面的節(jié)點(diǎn)的孩子節(jié)點(diǎn)（因?yàn)楸闅v前面的節(jié)點(diǎn)時(shí)，會彈出節(jié)點(diǎn)铜犬，同時(shí)將孩子節(jié)點(diǎn)壓入隊(duì)列）
通過上面的分析舞终，我們可以設(shè)置一個(gè)標(biāo)志位flag，當(dāng)子樹滿足完全二叉樹時(shí)癣猾，設(shè)置flag=YES敛劝。當(dāng)flag=YES而節(jié)點(diǎn)又破壞了完全二叉樹的條件，那么它就不是完全二叉樹煎谍。
/**
* 是否完全二叉樹
* 完全二叉樹：若設(shè)二叉樹的高度為h攘蔽，除第h層外，其它各層的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)呐粘，第h層有葉子結(jié)點(diǎn)满俗，并且葉子結(jié)點(diǎn)都是從左到右依次排布
*
* @param rootNode 根節(jié)點(diǎn)
*
* @return YES：是完全二叉樹，NO：不是完全二叉樹
*/
+ (BOOL)isCompleteBinaryTree:(TyBinaryTreeNode *)rootNode;
#pragma mark - 是否完全二叉樹
+ (BOOL)isCompleteBinaryTree:(TyBinaryTreeNode *)rootNode {
if (!rootNode) {
return NO;
}
//左子樹和右子樹都是空作岖，則是完全二叉樹
if (!rootNode.leftNode && !rootNode.rightNode) {
return YES;
}
//左子樹是空唆垃，右子樹不是空，則不是完全二叉樹
if (!rootNode.leftNode && rootNode.rightNode) {
return NO;
}
//按層次遍歷節(jié)點(diǎn)痘儡，找到滿足完全二叉樹的條件：
//條件1：如果某個(gè)節(jié)點(diǎn)的右子樹不為空辕万，則它的左子樹必須不為空
//條件2：如果某個(gè)節(jié)點(diǎn)的右子樹為空，則排在它后面的節(jié)點(diǎn)必須沒有孩子節(jié)點(diǎn)
//排在該節(jié)點(diǎn)后面的節(jié)點(diǎn)有2種：1）同層次的后面的節(jié)點(diǎn) 2）同層次的前面的節(jié)點(diǎn)的孩子節(jié)點(diǎn)（因?yàn)楸闅v前面的節(jié)點(diǎn)的時(shí)候沉删，會將節(jié)點(diǎn)從隊(duì)列里pop渐尿，同時(shí)把它的孩子節(jié)點(diǎn)push到隊(duì)列里）
NSMutableArray *queue = [NSMutableArray array];
[queue addObject:rootNode];
BOOL isComplete = NO; //是否已經(jīng)滿足完全二叉樹
while (queue.count > 0) {
TyBinaryTreeNode *node = [queue firstObject];
[queue removeObjectAtIndex:0];
//左子樹為空且右子樹不為空，則不是完全二叉樹
if (!node.leftNode && node.rightNode) {
return NO;
}
if (isComplete && (node.leftNode || node.rightNode)) {
//前面的節(jié)點(diǎn)已滿足完全二叉樹,如果還有孩子節(jié)點(diǎn)矾瑰，則不是完全二叉樹
return NO;
}
//右子樹為空砖茸，則已經(jīng)滿足完全二叉樹
if (!node.rightNode) {
isComplete = YES;
}
//壓入
if (node.leftNode) {
[queue addObject:node.leftNode];
}
if (node.rightNode) {
[queue addObject:node.rightNode];
}
}
return isComplete;
}
判斷二叉樹是否滿二叉樹
滿二叉樹定義為：除了葉結(jié)點(diǎn)外每一個(gè)結(jié)點(diǎn)都有左右子葉且葉子結(jié)點(diǎn)都處在最底層的二叉樹
滿二叉樹的一個(gè)特性是：葉子數(shù)=2^(深度-1)，因此我們可以根據(jù)這個(gè)特性來判斷二叉樹是否是滿二叉樹殴穴。
/**
* 是否滿二叉樹
* 滿二叉樹：除了葉結(jié)點(diǎn)外每一個(gè)結(jié)點(diǎn)都有左右子葉且葉子結(jié)點(diǎn)都處在最底層的二叉樹
*
* @param rootNode 根節(jié)點(diǎn)
*
* @return YES：滿二叉樹凉夯，NO：非滿二叉樹
*/
+ (BOOL)isFullBinaryTree:(TyBinaryTreeNode *)rootNode;
#pragma mark - 是否滿二叉樹
+ (BOOL)isFullBinaryTree:(TyBinaryTreeNode *)rootNode {
if (!rootNode) {
return NO;
}
//二叉樹深度
NSInteger depth = [self depthOfTree:rootNode];
//二叉樹葉子節(jié)點(diǎn)數(shù)
NSInteger leafNum = [self numberOfLeafsInTree:rootNode];
//滿二叉樹特性：葉子數(shù)=2^(深度-1)
if (leafNum == pow(2, (depth - 1))) {
return YES;
}
return NO;
}
判斷二叉樹是否平衡二叉樹
平衡二叉樹定義為：它是一棵空樹或它的左右兩個(gè)子樹的高度差的絕對值不超過1货葬，并且左右兩個(gè)子樹都是一棵平衡二叉樹。平衡二叉樹又叫AVL樹劲够。
/**
* 是否平衡二叉樹
* 平衡二叉樹：即AVL樹震桶，它是一棵空樹或它的左右兩個(gè)子樹的高度差的絕對值不超過1，并且左右兩個(gè)子樹都是一棵平衡二叉樹
*
* @param rootNode 根節(jié)點(diǎn)
*
* @return YES：平衡二叉樹征绎，NO：非平衡二叉樹
*/
+ (BOOL)isAVLBinaryTree:(TyBinaryTreeNode *)rootNode;
#pragma mark - 是否平衡二叉樹
+ (BOOL)isAVLBinaryTree:(TyBinaryTreeNode *)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;
}
