小肥柴慢慢手写数据结构（C篇）（5-3 树的遍历）

目录

5-10 BST/AVL的前序、中序和后序遍历

【先上暴论】若想学好递归，一定要从二叉树的遍历出发进行学习和训练，因为二叉树遍历的内核就是递归。

这是很多算法学习平台和大佬们给出的经验结论；但很多国内所谓学院派在讲授《数据结构（与算法）》这门课时，往往忽视了这层关键信息，只是吟唱：中左右（MLR）是前序遍历，左中右（LMR）是中序遍历，左右中（LRM）是后序遍历…

然后啪叽把一类经典二叉树考题甩人脸上：给定一个前序遍历序列和一个中序遍历序列，让大家在纸上重构出一颗二叉树…还顺带给出一些所谓的“考研口诀”…

个人不赞同上述行为，所以接下来的描述会显得有些啰嗦，希望大家耐心看下去。

以之前实现的带平衡因子的AVL树为基础开启问题讨论，先给出基础代码方便对照。
（1）h头文件

#ifndef _AVL_TREE_3
#define _AVL_TREE_3
typedef int ElementType;
struct AvlNode {
	ElementType Element;
    struct AvlNode *Left;
    struct AvlNode *Right;
    int Height;
};
typedef struct AvlNode *AvlTree;

//这个结构体是为了后面检测BST/AVL的有序性使用的，也可以使用ArrayList或者别的方式
struct LinkNode {
	ElementType data;
	struct LinkNode *next;
};
typedef struct LinkNode *Recorder;

AvlTree MakeEmpty(AvlTree T);
AvlTree Find(ElementType X, AvlTree T);
AvlTree FindMin(AvlTree T);
AvlTree FindMax(AvlTree T);
AvlTree Insert(ElementType X, AvlTree T);
AvlTree Delete(ElementType X, AvlTree T);
ElementType Retrieve(AvlTree T);

//下面这4个函数在编译时如果未实现请自己注释掉
void preOrder(AvlTree T);
void inOrder(AvlTree T);
void postOrder(AvlTree T);
int isOrder(AvlTree T);
#endif

（2）.c 具体实现（仅有基础部分，4个新函数另讲）

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "AvlTree.h"

AvlTree MakeEmpty(AvlTree T){
	if(T != NULL){
		MakeEmpty(T->Left);
		MakeEmpty(T->Right);
		free(T);
	}
	return NULL;
}

AvlTree Find(ElementType X, AvlTree T){
	if(T == NULL)
		return NULL;
		
	if(X < T->Element)
		return Find(X, T->Left);
	else if(X > T->Element)
		return Find(X, T->Right);
	else
		return T;
}

AvlTree FindMin(AvlTree T){
	if(T == NULL)
		return NULL;

	return (T->Left == NULL) ? T : FindMin(T->Left);
}

AvlTree FindMax(AvlTree T){
	if(T == NULL)
		return NULL;
	
	return (T->Right == NULL) ? T : FindMax(T->Right);
}

ElementType Retrieve(AvlTree T){
	return T->Element;
}

static int Height(AvlTree T){
   return (T == NULL) ? -1 : T->Height;
}

static int Max(int a, int b){
	return a > b ? a : b;
}

static void resetHeight(AvlTree T){
	if(T != NULL)
		T->Height = Max(Height(T->Left), Height(T->Right)) + 1;
}

static int caculatelBF(AvlTree T){
	return (T == NULL) ? 0 : (Height(T->Left) - Height(T->Right));
}

static AvlTree SingleRotateWithLeft(AvlTree K2){ //LL
	AvlTree K1 = K2->Left;
	K2->Left = K1->Right;
	K1->Right = K2;

	resetHeight(K2);
	resetHeight(K1);
	return K1;
}

static AvlTree SingleRotateWithRight(AvlTree K1){ //RR
	AvlTree K2 = K1->Right;
    K1->Right = K2->Left;
    K2->Left = K1;
	
	resetHeight(K1);
	resetHeight(K2);
    return K2;
}

static AvlTree DoubleRotateWithLeft(AvlTree K3){  //LR
	K3->Left = 	SingleRotateWithRight(K3->Left);
	return SingleRotateWithLeft(K3);
}

static AvlTree DoubleRotateWithRight(AvlTree K1){ //RL
	K1->Right = SingleRotateWithLeft(K1->Right);
	return SingleRotateWithRight(K1);
}

static AvlTree doBalance(AvlTree T){
	if(T == NULL)
		return NULL;
		
	resetHeight(T);
	int BF = caculatelBF(T);
	if(BF > 1){
		if(caculatelBF(T->Left) > 0)
			T = SingleRotateWithLeft(T);  // LL
		else
			T = DoubleRotateWithLeft(T);  // LR
	} 
	
	if(BF < -1){
		if(caculatelBF(T->Right) < 0)
			T = SingleRotateWithRight(T); // RR
		else
			T = DoubleRotateWithRight(T); // RL
	}

	return T;
}

AvlTree Insert(ElementType X, AvlTree T){
	if(T == NULL){
		T = malloc(sizeof(struct AvlNode));
		if(T == NULL){
			printf("Create AVL Tree ERROR\n");
			exit(0);
		}
		T->Element = X;
		T->Height = 0;
		T->Left = T->Right = NULL;
	} else if(X < T->Element){
		T->Left = Insert(X, T->Left);	
	} else if(X > T->Element){
		T->Right = Insert(X, T->Right);		
	}

	return doBalance(T);
}

AvlTree Delete(ElementType X, AvlTree T){
	if(T == NULL){
		printf("Tree is null, delete fail\n");
		return NULL;
	}
	
	if(X < T->Element){
	    T->Left = Delete(X, T->Left);
	} else if(X > T->Element){
		T->Right = Delete(X, T->Right);
	} else {
		AvlTree TmpCell;
		if(T->Left && T->Right){
			TmpCell = FindMin(T->Right);
			T->Element = TmpCell->Element;
			T->Right = Delete(T->Element, T->Right);
		} else {
			TmpCell = T;
			if(T->Left == NULL){
				T = T->Right;
			} else if(T->Right == NULL){
				T = T->Left;
			}
			free(TmpCell);
		}
	}

	return doBalance(T);
}

（3）用于测试的main

#include <stdio.h>
#include <stdlib.h>
#include "AvlTree.h"

int main(int argc, char *argv[]) {
    AvlTree T;
    int i, j;

    T = MakeEmpty(NULL);
    for(i = 0, j = 0; i < 15; i++, j = (j + 7) % 15){
		T = Insert(j, T);
	} 
	return 0;
}

（4）很容易得到上述插入的整数序列为：$[0,7,14,6,13,5,12,4,11,3,10,2,9,1,8]$，最后生成的平衡二叉树如下图：

5-10-1 直观理解有序二叉树的3种遍历

观察一个最小二叉树形结构单元，自然地想到对三个节点的访问顺序有三种（过于简单，没有必要标记顺序箭头）：

（1）root->left->right，“根节点=>左节点=>右节点”；
（2）left->root->right，“左节点=>根节点=>右节点”；
（3）left->right->root，“左节点=>右节点=>根节点”。

人们以访问根节点放在前后还是中间，来命名对应的遍历，即：
1）若先访问root，就是前序遍历。
2）若中间访问root，就是中序遍历。
3）若最后访问root，就是后序遍历。
看到这里或许有人会怼我了：“你这样介绍不也一样的人云亦云吗？”，别急。尝试写3个递归函数实现上述三种方式访问（用打印函数模拟动作）树中所有节点：

void preOrder(AvlTree T){
	if(T){
		printf("%d ", T->Element); //前序，先访问
		preOrder(T->Left);
		preOrder(T->Right);
	}
}

void inOrder(AvlTree T){
	if(T){
		inOrder(T->Left);
		printf("%d ", T->Element);
		inOrder(T->Right);
	}
}

void postOrder(AvlTree T){
	if(T){
		postOrder(T->Left);
		postOrder(T->Right);
		printf("%d ", T->Element);
	}
}

并在main中测试：

	printf("\nfinally:\n");
	printf("\npreOrder: ");
	preOrder(T);
	
	printf("\n\ninOrder: ");
	inOrder(T);	
	
	printf("\n\npostOrder: ");
	postOrder(T);	

可以得到如下输出：

由上述三种遍历的输出我们至少能得到两个浅显的结论：
（1）对有序树，中序遍历就是树中有序元素的顺序访问。
（2）对有序树，能够通过前序or后序遍历拿到树中有序元素的中位数，也是根节点所在。

沿着这两个看似浅显的结论继续思考：

（1）对有序树，中序遍历就是树中有序元素的顺序访问。

<1> 继续画图，一张图足以说明问题：

假设有道光从根节点7正上方往下照射，那么有序树印在地面的影子正好就是中序遍历的结果吗？哈哈哈，其实中序遍历可以换个角度去理解，其本质就是一种保序的映射啊！稍后讨论层序遍历会借用这个思路。

<2> 既然从根节点可以这样做，自然想到对子树如此操作可否？继续画图继续摸索。

i. 咱们单看左枝，左子树根节点为3，其左右两支的根节点也遵循上述规律。
ii. 这种拆分是相似的，符合递归的核心思想：将原始的大问题，按照某种规律不断拆分成小问题，直到拆分成可以解决的规模，于是整体问题可解；可以把下方的序列看成数组，数组被一部分一部分的劈开以解决问题，不是吗？

【重要的逆向思考】回到那个啪叽拍脸上那事儿，我们先看一个十分类似的问题：
【Q】若给定一个有序序列（即上图中底部的数组），如何恢复成一颗有序树呢？
【A】参考之前AVL树“拎起来”的操作，可以按照以下步骤执行：
step_1 直到中位数，把它拎起来作为root；且数组中所有在root左边的元素均为左子树的元素，反之所有在root右边的元素均为右子树的元素。
step_2 在root左边的子序列中重复上述操作，找到左子树root并拎起来；对root右边的子序列做相同操作。
step_3 继续划分左子树，重复上述操作；同理划分右子树。
step_4 可以操作的子序列长度越来越短，直到长度为1，说明已达叶子结点，操作结束。
【注】原谅我不会做动画，下面这张图将就一下。

既然知晓了这个性质，很快找到一个检测有序二叉树是否真的有序的办法：把中序遍历的结果都放入一个list中，最后检验list中所有元素是否有序即可，相关代码如下：

static void addLast(Recorder dummy, Recorder newNode){
	Recorder cur = dummy;
	while(cur->next)
		cur= cur->next;
	cur->next = newNode;
}

static void fillLink(AvlTree T, Recorder dummy){
	if(T){
		fillLink(T->Left, dummy);
		
		Recorder newNode = malloc(sizeof(struct LinkNode));
		if(newNode == NULL)
			exit(0);
		newNode->data = T->Element;
		newNode->next = NULL;
		addLast(dummy, newNode);
		
		fillLink(T->Right, dummy);
	}
}

int isOrder(AvlTree T){
	if(T == NULL)
		return 0;
	
	//虚拟头结点
	Recorder dummy = malloc(sizeof(struct LinkNode));
	if(dummy == NULL)
		exit(0);
	dummy->data = INT_MIN;
	dummy->next = NULL;
	
	//填充list
	fillLink(T, dummy);
	
	//遍历，检测有序性
	int ret = 1;
	Recorder cur = dummy;
	while(cur->next){
		if(cur->data > cur->next->data){
			ret = 0;
			break;
		}
		cur = cur->next;
	}
	
	//及时清理内存
//	printf("\n\n ==> get data link: ");
	cur = dummy;
	while(cur->next){
//		printf("%d ", cur->data);
		Recorder tmp = cur;
		cur = cur->next;
		free(tmp);
	}
//	printf("\n\n <<<<\n");
	return ret;
}

（2）对有序树，能够通过前序or后序遍历拿到树中有序元素的中位数，即根节点。

类比（1）的思路，给定前序遍历的序列（黄色标记root，蓝色标记left，红色标记right），继续探讨如何使用该序列还原二叉有序树的问题。大致思路如下图所示（后序遍历类似，不再赘述）：

具体规则描述如下：
<1> 每次子序列索引为0的元素即为root。
<2> 找到第一个大于root的元素，则从这个元素开始到序列最后的所有元素均在右子树上；在root和这个元素之间的所有元素均在左子树上。
<3> 继续划分并重复上述操作，直到子序列长度为1。（递归及其出口）

5-10-2 更加一般的规律

上一小节描述的对有序二叉树是完全适用的，只是再进一步思索会发现新问题：
（1）中序遍历找root需要遍历一次数组，或者在拿到数组长度的情况下直接计算索引，才能确认左右子树的元素所在位置；前序遍历能够很容易拿到root，但是需要遍历比较之后才能确认左右子树元素所在位置；这两种情况处理起来并没有那么清爽。
（2）如果问题难度升级：给定的不再是有序树，而是一般的二叉树呢？缺失了“有序”这个条件之后是否能够还原成功？

既然咱们敢把大家往这个思路上引导，必然是前人已经研究过这个问题并给出了合理的解决方案了！
【Q】试想：二叉树不是可以映射为一个序列吗？咱们不是提到过用空间可以换时间吗？那么如果给出了同一颗二叉树的前序遍历+中序遍历 or 后序遍历+中序遍历 的序列组合，是否能解决上述疑问呢？
【A】抓住序列的特点：索引（数组下标）试试总结规律。


继续拆分（递归）

…大家可以自己按照上面的图示多试验几次，很容易发现如下规律：
（1）root = preOrder[0] = inOrder[index]
（2）left = preOrder[1] ~ preOrder[index]， left = inOrder[0] ~ inOrder[index -1]
（3）right = preOrder[index+1] ~ preOrder[size]，right = inOrder[index+1] ~ inOrder[size]
（4）下一轮递归， left_size = index, right_size = size - index - 1，可以借助索引确定子序列长度（仅部分使用，老套路）

其实这个问题在LeeCode上是有对应题目的：

【LCR 124. 推理二叉树】某二叉树的先序遍历结果记录于整数数组 preorder，它的中序遍历结果记录于整数数组 inorder。请根据 preorder 和 inorder 的提示构造出这棵二叉树并返回其根节点。

函数签名如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* deduceTree(int* preorder, int preorderSize, int* inorder, int inorderSize) {
    
}

按照上面讨论的内容，很容易就能完成如下代码：

struct TreeNode* deduceTree(int* preorder, int preorderSize, int* inorder, int inorderSize) {
    if(preorderSize <= 0 || inorderSize <= 0)
        return NULL;
	
	//从preOrder[0]处获取根节点
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = preorder[0];
    root->left = NULL;
    root->right = NULL;

    //找到inOrder[]中根节点的位置
    int index;
    for(index = 0; index < inorderSize; index++){
        if(preorder[0] == inorder[index])
            break;
    }

	//左右两支递归
    root->left = deduceTree(preorder+1, index, inorder, index);
    root->right = deduceTree(preorder+index+1, preorderSize-index-1, inorder+index+1, inorderSize-index-1);

    return root;
}

5-11 再看二叉树的前/中/后序遍历

再次重申本系列的核心观点：学习数据结构的目的是为了加快某些场景下的某些问题的解决速度，只有把应用题做好，才算是真的学懂弄通。

咱们先看几个LeeCode上二叉树的经典应用（我也很赞同去搜历年408考研题，部分题目的技术含量接近大厂面试数据结构与算法部分题目的水准），在熟悉如何使用二叉树递归特性后再重新认识和总结二叉树的递归框架。

5-11-1 经典问题热身

【100. 相同的树】给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

函数签名：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    
}

【思路】
（1）比较两棵树是否相同，第一步肯定是对比根节点。
（2）接下来对比左子树，对比右子树。

是不是和前序遍历的访问顺序很像？很快给出答案：

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
	//前序遍历，先看root
	// 情况1：两个都是空树
    if(p == NULL && q == NULL)
        return true;
    //情况2：一个为空，一个不为空
    if(p == NULL || q == NULL)
        return false;
    //情况3：都不为空，开始比较val
    if(p->val != q->val)
        return false;
    //分别遍历左子树和右子树
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

【LCR 144. 翻转二叉树】给定一棵二叉树的根节点 root，请左右翻转这棵二叉树，并返回其根节点。

函数签名：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


struct TreeNode* mirrorTree(struct TreeNode* root){

}

【思路】
（1）根节点不用变动，但是需要判断是否到头（叶子结点的左右子树为空！）
（2）拿到左节点，扔给函数递归镜像；拿到右节点，扔给函数递归镜像。
（3）返回根节点，完事！

嘿嘿，这不又是一个前序遍历嘛！

struct TreeNode* mirrorTree(struct TreeNode* root){
    if(root == NULL)
        return root;
    
    struct TreeNode* left = root->left;
    struct TreeNode* right = root->right;

    root->left = mirrorTree(right);
    root->right = mirrorTree(left);

    return root;
}

【104. 二叉树的最大深度】给定一个二叉树 root ，返回其最大深度；最大深度是指从根节点到最远叶子节点的最长路径上的节点数。

函数签名

int calculateDepth(struct TreeNode* root) {
    
}

类似前面两道题，可用后续遍历思维解决：最大深度 = 左右枝的最大深度 + 1（root），完事。

int calculateDepth(struct TreeNode* root) {
    if(root == NULL)
        return 0;

    int leftDepth = calculateDepth(root->left);
    int rightDepth = calculateDepth(root->right);

    return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}

5-11-2 二叉树递归框架

通过以上问题梳理、推导和对应简单编程实践，现在可以直接给出二叉树递归的框架了：

void traverse(TreeNode root) {
	//前序遍历代码放在这里：要对root做些什么
	traverse(root->left);
	//中序遍历代码放在这里：要对root做些什么	
	traverse(root->right);
	//后序遍历代码放在这里：要对root做些什么
}

即所谓二叉树的前/中/后序遍历，就是要在两段逻辑：traverse(root->left)和traverse(root->right)提供的三处位置视情况添加我们要处理当前节点的代码，仅此而已。

大家都知道递归是依靠压栈实现的，那么如果跟着压栈/出栈的顺序，细心研究最小单元中的访问顺序，你会有新的发现：无论哪种遍历，root会被路过两次哦！

这个性质主要有两个用处：
（1）一些问题中（特别是考研题），要求借用stack用非递归的方式去实现这三种遍历。
（2）利用2/4两个访问顺序的指向（其实就是回溯），实现“自底向上”的访问方式。

5-11-3 再看3种遍历

（1）非递归（迭代）实现前序遍历

【144. 二叉树的前序遍历】给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

函数签名

int* preorderTraversal(struct TreeNode* root, int* returnSize) {

}

解决方案很简单，对当前root压栈，先处理左枝（cur = cur->left） ，接着root出栈，继续处理右枝（cur = cur->right）

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int *res = (int *)malloc(sizeof(int) * 200);
    struct TreeNode* stack[200];
    int top = -1;
    struct TreeNode* cur = root;
    *returnSize = 0;

    while(cur || top != -1){
        while(cur){
            res[(*returnSize)++] = cur->val;
            stack[++top] = cur;
            cur = cur->left;
        }
        // cur为空，那么只可能是叶子，开始处理当前根节点右枝
        if(top !=-1){
            cur = stack[top--];
            cur = cur->right;
        }
    }

    return res;
}

（2）非递归（迭代）实现中序遍历

【94. 二叉树的中序遍历】给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

函数签名

int* inorderTraversal(struct TreeNode* root, int* returnSize) {

}

调整将当前根塞入结果数组res这段逻辑的位置，在遇到左节点为NULL后再记录。

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    int *res = (int *)malloc(sizeof(int) * 200);
    struct TreeNode* stack[200];
    int top = -1;
    struct TreeNode* cur = root;
    *returnSize = 0;

    while(cur || top != -1){
        while(cur){
            stack[++top] = cur;
            cur = cur->left;
        }
        if(top !=-1){
            cur = stack[top--];
            res[(*returnSize)++] = cur->val;
            cur = cur->right;
        }
    }

    return res;
}

（3）非递归（迭代）实现后续遍历

【145. 二叉树的后序遍历】给你一棵二叉树的根节点 root ，返回其节点值的 后序 遍历 。

函数签名

int* postorderTraversal(struct TreeNode* root, int* returnSize) {

}

后续遍历的非递归实现不同于前序遍历和中序遍历，因为从给出的顺序图可以看到root要模拟2次压栈和1次出栈（图中rooy->1->2->root->3->4->root）。我们可以设置一个前置标记prev用于记录是否已经遍历完右节点，确认遍历完成才会往res中添加当前root的数据。

int* postorderTraversal(struct TreeNode* root, int* returnSize) {
        int *res = (int *)malloc(sizeof(int) * 200);
    struct TreeNode* stack[200];
    int top = -1;
    struct TreeNode* cur = root;
    struct TreeNode* prev = NULL;
    *returnSize = 0;

    while(cur || top != -1){
        while(cur){ 
            stack[++top] = cur;
            cur = cur->left;
        }
        cur = stack[top--];
        if(cur->right == NULL || cur->right == prev){
            res[(*returnSize)++] = cur->val;
            prev = cur;
            cur = NULL;
        } else {
            stack[++top] = cur;
            cur = cur->right;
        }
    }

    return res;
}

【注】其实还有一种Morris遍历方法实现上述3种遍历，有机会单开一帖讨论。

5-11-4 尝试解决复杂问题

在网络项目（或者分布式项目，例如Hadoop）中常用的算法：计算两个节点的最近共同祖先问题（LCA），此问题就是典型的“自底向上”访问。

【236. 二叉树的最近公共祖先】给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

函数签名

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q){

}

如下图示：节点2和节点4的LCA为节点3，节点2和节点5的LCA也是3，二而节点0和节点8的LCA是7。
【思路】

【参考《代码随想录》和K神的题解】：
（1）如果能够自底向上般地搜索LCA是比较符合常规思维的，翻看之前讨论的内容，优先采用后续遍历，借助两次回到root的特性去处理该问题比较合适。
（2）判定当前节点root是否为给定的两个节点p、q的根节点规律如下：
<1> 若p、q分别在root左右子树中，那么root必定是最近公共祖先。
<2> 若root=p，且q在root的子树中；同理若root=q，且p在root的子树中。

【参考《代码随想录》中的描述】递归“三部曲”
（1）确定递归函数和返回参数： struct TreeNode* lowestCommonAncestor(root, p, q)
（2）确定终止条件：root为空（root == NULL）、找到了p或q（root == p || root == q）
（3）确定单层递归逻辑：分别遍历left和right两颗子树，left = LCA(root->left)，right= LCA(root->right)

得到最后答案：

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    if(root == NULL || root == q || root == p)
        return root;

    struct TreeNode* left = lowestCommonAncestor(root->left, p, q);
    struct TreeNode* right = lowestCommonAncestor(root->right, p, q);

    if(left && right)
        return root;
    else if(left && right == NULL)
        return left;
    else if(right && left == NULL)
        return right;
    else
        return NULL;
}

【注】当然，此问题还有更加优秀的解法，但我依旧认为上述递归解法是最自然的。

再看一个类似的问题：

【235. 二叉搜索树的最近公共祖先】给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

函数签名

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    
}

【思路】参考上一题思路，利用BST有序的原理去判断p、q是否在同侧还是异侧。
（1）若 $root?p$ 与 $root?q$ 异号，则p、q在异侧，root即为所求。
（2）若 $root?p$ 、$root?q$ 中有一个为0，说明p、q就是root，直接返回root。
（3）若 $root?p$ 与 $root?q$ 同号，则p、q在同侧，还要继续往下找。

解题代码如下（测试用例用需要考虑int溢出，改为long或者double类型）：

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    long val1 = (long)root->val-(long)p->val;
    long val2 = (long)root->val-(long)q->val;
    if(val1*val2 <= 0) 
        return root; 
    return lowestCommonAncestor(p->val< root->val? root->left :root->right ,p,q);
}

此外，还有一个更加有挑战的问题【LeeCode 297 二叉树的序列化与反序列化】，有兴趣可以试试看。

5-11-5 深度优先搜索（DFS）与二叉树遍历浅谈

关于DFS，咱们在之前讲Stack解决迷宫问题时提到过，具体内容就不在重复了；第一次学习树的遍历，对于前中后三种遍历方式充分掌握之后，必然可以将DFS与其关联起来，即“一条道走到黑”（深度优先搜索的“深”），先遍历完左子树（直到最左边，不一定是叶子结点），在遍历右子树（直到最右边，不一定是叶子结点），十分容易理解；后续讲到“图”的时候再正式讨论。

5-12 层序遍历

顾名思义，按照树中的每一层作为一次遍历的单元去执行，如下图从root开始，不同层的最后一个元素执行遍历之后，才开始进入下一层的遍历。

5-12-1 层序遍历的原理

有了前面的遍历操作经验，层序遍历的思路就相对简单了：
（1）对每个当前root，需要遍历它的left和right；
（2）若希望继续遍历left和right的下一层中left的左右节点，必然需要在遍历right的左右节点前，记录下left->left和left->right的地址；同理，对right的左右节点也需要缓存。
（3）从记录开始，继续下一层的遍历。

由上分析可知，需要选用一种合适的存储方式按顺序暂时缓存以上四个节点地址；且按顺序使用完后要删除。那使用哪种存储方式合适呢？

嘿嘿，自然是队列啦！如下图：

（1）每次当前层的所有节点入队。
（2）出队遍历各个节点。
（3）每出队一个节点，将这个节点的left和right入队。
循环往复上述过程，直到遍历完所有节点。

5-12-2 层序遍历队列实现

（1）AvlTree.h，删除了不必要的函数

#ifndef _AVL_TREE_4
#define _AVL_TREE_4
struct AvlNode {
	int Element;
    struct AvlNode *Left;
    struct AvlNode *Right;
    int Height;
};
typedef struct AvlNode *AvlTree;

AvlTree MakeEmpty(AvlTree T);
AvlTree Insert(int X, AvlTree T);
AvlTree Delete(int X, AvlTree T);
int Retrieve(AvlTree T);

void levelOrder(AvlTree T);
#endif

（2）AvlTree.c，调整了一些实现，重点看 void levelOrder(AvlTree T)

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "AvlTree.h"
#include "Queue.h"
AvlTree MakeEmpty(AvlTree T){
	if(T != NULL){
		MakeEmpty(T->Left);
		MakeEmpty(T->Right);
		free(T);
	}
	return NULL;
}

static AvlTree Find(int X, AvlTree T){
	if(T == NULL)
		return NULL;
		
	if(X < T->Element)
		return Find(X, T->Left);
	else if(X > T->Element)
		return Find(X, T->Right);
	else
		return T;
}

static AvlTree FindMin(AvlTree T){
	if(T == NULL)
		return NULL;

	return (T->Left == NULL) ? T : FindMin(T->Left);
}

static AvlTree FindMax(AvlTree T){
	if(T == NULL)
		return NULL;
	
	return (T->Right == NULL) ? T : FindMax(T->Right);
}

int Retrieve(AvlTree T){
	return T->Element;
}

static int Height(AvlTree T){
   return (T == NULL) ? -1 : T->Height;
}

static int Max(int a, int b){
	return a > b ? a : b;
}

static void resetHeight(AvlTree T){
	if(T != NULL)
		T->Height = Max(Height(T->Left), Height(T->Right)) + 1;
}

static int caculatelBF(AvlTree T){
	return (T == NULL) ? 0 : (Height(T->Left) - Height(T->Right));
}

static AvlTree SingleRotateWithLeft(AvlTree K2){ //LL
	AvlTree K1 = K2->Left;
	K2->Left = K1->Right;
	K1->Right = K2;

	resetHeight(K2);
	resetHeight(K1);
	return K1;
}

static AvlTree SingleRotateWithRight(AvlTree K1){ //RR
	AvlTree K2 = K1->Right;
    K1->Right = K2->Left;
    K2->Left = K1;
	
	resetHeight(K1);
	resetHeight(K2);
    return K2;
}

static AvlTree DoubleRotateWithLeft(AvlTree K3){  //LR
	K3->Left = 	SingleRotateWithRight(K3->Left);
	return SingleRotateWithLeft(K3);
}

static AvlTree DoubleRotateWithRight(AvlTree K1){ //RL
	K1->Right = SingleRotateWithLeft(K1->Right);
	return SingleRotateWithRight(K1);
}

static AvlTree doBalance(AvlTree T){
	if(T == NULL)
		return NULL;
		
	resetHeight(T);
	int BF = caculatelBF(T);
	if(BF > 1){
		if(caculatelBF(T->Left) > 0)
			T = SingleRotateWithLeft(T);  // LL
		else
			T = DoubleRotateWithLeft(T);  // LR
	} 
	
	if(BF < -1){
		if(caculatelBF(T->Right) < 0)
			T = SingleRotateWithRight(T); // RR
		else
			T = DoubleRotateWithRight(T); // RL
	}

	return T;
}

AvlTree Insert(int X, AvlTree T){
	if(T == NULL){
		T = malloc(sizeof(struct AvlNode));
		if(T == NULL){
			printf("Create AVL Tree ERROR\n");
			exit(0);
		}
		T->Element = X;
		T->Height = 0;
		T->Left = T->Right = NULL;
	} else if(X < T->Element){
		T->Left = Insert(X, T->Left);	
	} else if(X > T->Element){
		T->Right = Insert(X, T->Right);		
	}

	return doBalance(T);
}

AvlTree Delete(int X, AvlTree T){
	if(T == NULL){
		printf("Tree is null, delete fail\n");
		return NULL;
	}
	
	if(X < T->Element){
	    T->Left = Delete(X, T->Left);
	} else if(X > T->Element){
		T->Right = Delete(X, T->Right);
	} else {
		AvlTree TmpCell;
		if(T->Left && T->Right){
			TmpCell = FindMin(T->Right);
			T->Element = TmpCell->Element;
			T->Right = Delete(T->Element, T->Right);
		} else {
			TmpCell = T;
			if(T->Left == NULL){
				T = T->Right;
			} else if(T->Right == NULL){
				T = T->Left;
			}
			free(TmpCell);
		}
	}

	return doBalance(T);
}

void levelOrder(AvlTree T){
	if(T == NULL)
		return;
		
	Queue Q = CreateQueue(20);
	Enqueue(T, Q);
	
	while(Q->Size > 0){
		AvlTree cur = Front(Q);
		printf(" %d ", cur->Element);
		Dequeue(Q);
		if(cur->Left)
			Enqueue(cur->Left, Q);
		if(cur->Right)
			Enqueue(cur->Right, Q);
	}
	
	DisposeQueue(Q);
}

（3）Queue.h，简化的队列

#include "AvlTree.h"
#ifndef _Queue_Array_h
#define _Queue_Array_h
struct QueueRecord{
    int Capacity;
    int Front;
    int Rear;
    int Size;
    struct AvlNode *Array;
};
typedef struct QueueRecord *Queue;

Queue CreateQueue(int MaxElements);
void DisposeQueue(Queue Q);
void Enqueue(struct AvlNode *X, Queue Q);
void Dequeue(Queue Q);
struct AvlNode *Front(Queue Q);
#endif  /* _Queue_h */

（4）Queue.c，注意入队元素是节点，因为需要再出队列时加入后续的信息！

#include <stdio.h>
#include <stdlib.h>

#include "Queue.h"

#define MinQueueSize ( 10 )

static int IsEmpty(Queue Q){
	return Q->Size == 0;
}

static int IsFull(Queue Q){
    return Q->Size == Q->Capacity;
}

static void MakeEmptyQueue(Queue Q){
    Q->Size = 0;
    Q->Front = 1;
    Q->Rear = 0;
}

Queue CreateQueue(int MaxElements){
    Queue Q = NULL;
    if(MaxElements < MinQueueSize)
    	MaxElements = MinQueueSize;

    Q = malloc(sizeof(struct QueueRecord));
    if(Q == NULL){
    	printf( "Out of space!!!\n" );
    	exit(0);
	}

    Q->Array = malloc(sizeof(struct AvlNode) * MaxElements);
    if(!Q->Array){
	    printf( "Out of space!!!\n" );
	    free(Q);
	    exit(0);
	}

    Q->Capacity = MaxElements;
    MakeEmptyQueue(Q);

    return Q;
}

void DisposeQueue(Queue Q){
    if(Q){
        free(Q->Array);
        free(Q);
    }
}

static int Succ(int Value, Queue Q){
    if(++Value == Q->Capacity)
        Value = INT_MIN;
    return Value;
}

static void resizeQueue(Queue Q, int len){
	int *newArray = malloc(sizeof(struct AvlNode) * len);
	int *oldArray = Q->Array;
	int i;
	for(i = 0; i < len; i++)
		newArray[i] = oldArray[i];
	
	Q->Array = newArray;
	free(oldArray);
	Q->Capacity = len;
}

void Enqueue(struct AvlNode *X, Queue Q){
    if(IsFull(Q)){
    	resizeQueue(Q, Q->Capacity<<1);
	} else {
        Q->Size++;
        Q->Rear = Succ(Q->Rear, Q);
        Q->Array[Q->Rear] = *X;
    }
}

void Dequeue(Queue Q){
    if(IsEmpty(Q))
        printf("Empty queue\n");
    else {
        Q->Size--;
        Q->Front = Succ(Q->Front, Q);
        
		if((Q->Size > MinQueueSize) && (Q->Size < Q->Capacity / 4))
			resizeQueue(Q, Q->Capacity>>1);
    }
}

struct AvlNode *Front(Queue Q){
    if(!IsEmpty(Q))
        return &Q->Array[Q->Front];
    printf( "Empty queue\n" );
    return NULL;
}

（5）测试代码main.c和测试结果

#include <stdio.h>
#include <stdlib.h>

#include "AvlTree.h"

int main(int argc, char *argv[]) {
	AvlTree T;
    int i, j;

    T = MakeEmpty(NULL);
    for(i = 0, j = 0; i < 15; i++, j = (j + 7) % 15){
    	printf("\ninsert: %d", j);
		T = Insert(j, T);
	}
	
	printf("\nlevel order:\n");
	levelOrder(T);
	return 0;
}

5-12-3 层序遍历数组实现

这个方法仅仅是为了告诉大家：
（1）学习数据结构，一定不要去背代码，还要根据实际情况轻量化数据结构，从应用的角度去施展内功心法。
（2）同之前讨论过的Stack、Queue等等数据结构一样，Tree的存储方式和操作的底层实现也可以用Array（当然具体完全体是堆，咱们这里仅仅是做一个平滑的讨论与引入）。
（3）在实际项目中使用的数据结构，要么是已经写好的标准通用型数据结构，要么就是简陋的不能再简陋的数组/链表（此处就当为下一贴阶段性讨论做铺垫吧）。

【注】我们可简单认为当前Tree是满树，先划定一个合理的数组空间$$capacity=2^{height}?1$$（实际用指针表示），接着使用head和tail模拟出队和入队，注意偏移。

AvlTree.h 与上一小节一致；对AvlTree.c，仅给出level函数相关实现，其他参考之前的代码

static int Pow(int X, unsigned int N){
	int res =  1;
	while(N > 0){
		if(N & 0x1 == 1)
			res *= X;
		N >>= 1;
		X *= X;
	}
	return res;
}

void levelOrder(AvlTree T){
	if(T == NULL)
		return;
		
	int capacity = Pow(T->Height,2);
	struct AvlNode *queue = malloc(sizeof(struct AvlNode) * capacity);
	int head = 0;
	int tail = 0;
	queue[tail++] = *T;
	
	int i;
	while(head != tail && tail < capacity){
		int start = head;
		head = tail;
		for(i = start; i < tail; i++){
			printf(" %d", queue[i].Element);
			if(queue[i].Left)
				queue[tail++] = *(queue[i].Left);
			if(queue[i].Right)
				queue[tail++] = *(queue[i].Right);
		}	
	}
}

【注】可以用LeeCode 102 二叉树的层序遍历来练习

【102. 二叉树的层序遍历】给你二叉树的根节点 root ，返回其节点值的 层序遍历 （即逐层地，从左到右访问所有节点）。

函数签名

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {
    
}

【（借鉴大神的）核心思路】
（1）用数组 ans[ ] 记录最后输出结果，主要是应对测试用例的边界问题。
（2）合理使用索引偏移，应对输出结果中的每层的数量问题，要求比我们自己做的实验要严格很多。

#define max_num 2000
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes)
{
	// early return，对应测试用例边界
    *returnSize = 0;
    if(!root) 
        return NULL;

    int **ans = (int**)malloc(sizeof(int*) * max_num); //此时只是申请的行数
    int columnSizes[max_num];

    struct TreeNode *queue[max_num];  //放入数的队列
    int head = 0, rear = 0;
    queue[rear++] = root;  //录入根结点
    
    int i;
    while(rear != head){ //队列不为空
        //确定改行的列数
        int curLen = rear - head;
        ans[(*returnSize)] = (int*)malloc(sizeof(int*) * curLen); 
        columnSizes[(*returnSize)] = curLen;
        int start = head;//记录该层的起点，并将head移动到下一层的起点
        head = rear;
        for(i = start; i < head; i++){//出队并记录每层树的值
            ans[(*returnSize)][i-start] = queue[i]->val;
            if(queue[i]->left)
                queue[rear++] = queue[i]->left;
            if(queue[i]->right)
                queue[rear++] = queue[i]->right;
        }
        (*returnSize)++;
    }
    *returnColumnSizes = (int*)malloc(sizeof(int) * (*returnSize));
    for(i = 0; i < *returnSize; i++) //确定每层节点数
        (*returnColumnSizes)[i] = columnSizes[i];
    return ans;
}

另一个经典问题，可以考虑由上题出发，反向放置输出答案，有意向的朋友可以尝试一下。

【107. 二叉树的层序遍历 II】给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

5-12-4 层序遍历与广度优先搜索（BFS）浅谈

（1）层序遍历是BFS，这个观点是大家都认可的，点到为止。
（2）后续的学习和讨论中，大家会看到这种底层依赖数组实现的“抽象的树结构”，就是人们常说的“堆”，可以看做特殊的树或者树的衍生形态。
【注】个人感觉写这些小标题有点脱了裤子放屁的味道…其实我们也可以在本篇之初就给定这些概念或者推论，可若没有一个平滑的引入，直接介绍知识点或许会显得有些粗暴。

5-13 批斗一下线索树

讨论二叉树遍历，线索树往往会被提及。（参看文献[5]）虽然线索树这个衍生数据结构对训练思维很有用，绕来绕去的，但实用性不高（理论上的完备性不够），再讲一个暴论：也就是考研喜欢这种非常磨人的东西，呵呵；反正我看清华大学邓版的教程里（包括公开的视频教程）压根没提这块知识点，黑皮书也仅仅将其作为一个课下训练题。

引用一下文献[5]中提出的两个负面观点：

参考文献和资料

[1]《代码随想录》
[2] labuladong相关博客
[3] liuyubobo相关博客
[4] LeeCode题解
[5] 林和平，周颜军，李永旭. 线索二叉树[J]. 吉林大学学报，2005(23).