[数据结构与算法]LeetCode Day 2：树

树的建立

首先定义树的节点TreeNode。同样的，该结构为最简单的二叉树，若要定义n叉树，可以使用STL库的map<int, TreeNode*>，此处先讨论最简单的二叉树。

 * typedef struct {
 * 	   // 节点的值
 *     int val;
 * 	   // 左孩子
 *     struct TreeNode *left;
 *     // 右孩子
 *     struct TreeNode *right;
 * } TreeNode;

再定义树本身的结构

 * typedef struct {
 *     struct TreeNode *root;
 * } Tree;

二叉树的遍历

二叉树的中序遍历

递归实现

二叉树中序遍历的递归实现非常简单，只需从根节点开始，递归调用中序遍历函数inorder。对于每个节点来说，都对以自身为根节点的子树进行中序遍历（遍历顺序为左孩子->自身->右孩子）。中序遍历的递归实现代码如下：

void inorder(struct TreeNode* root, int* array, int* returnSize) {
	/*
		node：根节点，下列函数将以node为根节点，对子树进行中序遍历
		array：中序遍历数组（遍历结果）
		returnSize：在递归调用中维护数组的大小
	*/
    if (!root) {
    	// 对于NULL节点，立即返回
        return;
    }
    // 先对左孩子进行中序遍历
    inorder(root->left, array, returnSize);
    // 再遍历自身，维护数组的大小
    array[*returnSize] = node->val;
    *returnSize = *returnSize + 1;
    // 最后对右孩子进行中序遍历
    inorder(root->right, array, returnSize);
}

int* inorderTraversal(struct TreeNode* root, int* returnSize){
	/*
		root：二叉树的根节点
		returnSize：返回的遍历数组的大小
	*/
	// 分配一段内存，用于存储遍历的节点值
    int* array = (int *)malloc(101 * sizeof(int));
    // 初始化数组的大小为0
    (*returnSize) = 0;
    // 对以root为根节点的二叉树进行中序遍历
    inorder(root, array, returnSize);
    return array;
}

普通迭代实现

递归实现中，编译器为我们隐式地维护了一个栈。因此在迭代实现中，我们需要把这个栈模拟出来。

迭代的思想如下：

• 由于每个节点的左孩子一定比节点本身要更早被遍历，因此某个节点可以被遍历当且仅当（1）该节点的左孩子被遍历；或者（2）该节点没有左孩子。
• 显然条件（2）是我们的突破口。因此我们设计一个栈，从根节点开始向下，向左找到第一个没有左孩子的树节点（边找边压栈）。
• 压栈的原因？： 栈中的节点都是由于其左孩子未被遍历，而等待被遍历的树节点，每个节点的左孩子都在它所在栈的位置的上方。因此节点在栈顶当且仅当它的左孩子已经被遍历，此时符合上述条件（1）。换句话说：节点在栈顶当且仅当该节点可以被遍历。
• 综上所述，中序遍历的思想是：①将等待被遍历的树节点压入栈中，再将该节点被遍历的前置节点压入栈中，如此类推。②当找到一个没有前置节点（或前置节点被遍历）的节点时，这样的节点一定位于栈顶，此时将该节点弹栈，并放入遍历数组中。③当本节点被遍历后，将当前节点迭代为节点的右孩子，以此为根继续进行遍历；④当栈空且当前节点为空时，遍历结束。

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize = 0;
    int* array = malloc(sizeof(int) * 101);
    // stk：我们要维护的栈
    struct TreeNode** stk = malloc(sizeof(struct TreeNode*) * 101);
    // top：栈顶指针
    int top = 0;
    while (root != NULL || top > 0) {
        while (root != NULL) {
        	/* 
        		向下遍历，同时将等待被遍历的节点压栈。
			*/
            stk[top++] = root;
            root = root->left;
        }
        // 压栈完成，将栈顶的节点放入遍历数组中
        root = stk[--top];
        array[(*returnSize)++] = root->val;
        // 最后将节点迭代成右孩子
        root = root->right;
    }
    return array;
}

Morris中序遍历（*了解）

// 该中序遍历方法需要修改树结构
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    int* res = malloc(sizeof(int) * 501);
    *returnSize = 0;
    struct TreeNode* predecessor = NULL;

    while (root != NULL) {
        if (root->left != NULL) {
            // predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止
            predecessor = root->left;
            while (predecessor->right != NULL && predecessor->right != root) {
                predecessor = predecessor->right;
            }

            // 让 predecessor 的右指针指向 root，继续遍历左子树
            if (predecessor->right == NULL) {
                predecessor->right = root;
                root = root->left;
            }
            // 说明左子树已经访问完了，我们需要断开链接
            else {
                res[(*returnSize)++] = root->val;
                predecessor->right = NULL;
                root = root->right;
            }
        }
        // 如果没有左孩子，则直接访问右孩子
        else {
            res[(*returnSize)++] = root->val;
            root = root->right;
        }
    }
    return res;
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/binary-tree-inorder-traversal/solution/er-cha-shu-de-zhong-xu-bian-li-by-leetcode-solutio/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

二叉树的前序遍历

递归实现

void preorder(struct TreeNode* root, int* array, int* returnSize) {
    if (!root) {
        return;
    }
    array[(*returnSize)++] = root->val;
    preorder(root->left, array, returnSize);
    preorder(root->right, array, returnSize);
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    int* array = (int*) malloc(101 * sizeof(int));
    *returnSize = 0;
    preorder(root, array, returnSize);
    return array;
}

迭代实现

对于二叉树前序遍历的迭代实现，我们依然采用栈模拟的方式，遍历思想如下：

1. 将当前节点的值放入遍历数组中
2. 因为左子树尚未被遍历，右孩子需要压入栈中等待
3. 访问左孩子，若没有左孩子，则访问栈中的节点
4. 若栈空且当前节点为NULL，遍历结束

int* preorderTraversal(struct TreeNode* root, int* returnSize){
    int* array = (int*) malloc(101 * sizeof(int));
    *returnSize = 0;
    struct TreeNode** stk = (struct TreeNode**) malloc(101 * sizeof(struct TreeNode*));
    int top = 0;
    struct TreeNode* cur = root;
    while (top != 0 || cur) {
        if (cur) {
        	// 访问当前节点
            array[(*returnSize)++] = cur->val;  // 遍历自身
            if (cur->right) {
            	// 将右孩子压栈
                stk[top++] = cur->right;
            }
            // 访问左孩子，进入下一次循环
            cur = cur->left;
        } else {
        	// 访问栈顶节点
            cur = stk[--top];
        }
    }
    return array;
}

二叉树的后序遍历

递归实现

void postorder(struct TreeNode* root, int* array, int* returnSize) {
    if (!root) {
        return;
    }
    postorder(root->left, array, returnSize);
    postorder(root->right, array, returnSize);
    array[(*returnSize)++] = root->val;
}
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* postorderTraversal(struct TreeNode* root, int* returnSize){
    int* array = (int*) malloc(101 * sizeof(int));
    *returnSize = 0;
    postorder(root, array, returnSize);
    return array;
}

迭代实现

后序遍历的迭代实现比前两种都复杂。主要复杂的点在于：在左子树遍历完成以后，栈顶节点不一定是被遍历的节点，需要判断它的右子树是否已经遍历完成。为了达到这一目的，需要增加临时变量prev，用来标记上一个被遍历的节点。在此基础上，我们梳理后序遍历的思路如下：

• 迭代地向下访问左孩子，直到某个节点没有左孩子，将其作为当前节点。在向下访问的过程中将访问到的节点进行压栈处理。
• 此时需要判断：如果当前节点没有右孩子，或者prev节点是右孩子（说明右子树已经遍历完成），则遍历当前节点。否则，将当前节点压栈，并访问右孩子。
• 当栈空且当前节点为NULL时，遍历结束

代码实现如下：

int* postorderTraversal(struct TreeNode* root, int* returnSize){
    int* array = (int*) malloc(101 * sizeof(int));
    *returnSize = 0;
    if (!root) {
        return array;
    }
    struct TreeNode** stk = (struct TreeNode**) malloc(101 * sizeof(struct TreeNode*));
    int top = 0;
    struct TreeNode* cur = root;
    struct TreeNode* prev = NULL;
    while(top > 0 || cur) {
        // 找到最左的节点
        while (cur != NULL) {
            stk[top++] = cur;
            cur = cur->left;
        }
        cur = stk[--top];
        // 判断是否有右子树/右子树是否已经被遍历
        if (cur->right == NULL || cur->right == prev) {
            // 没有右子树或右子树已经被遍历，遍历自己
            array[(*returnSize)++] = cur->val;
            // 维护prev节点的值
            prev = cur;
            // 将当前节点置为NULL，等待下一轮循环取栈顶节点
            cur = NULL;
        } else {
            // 将当前节点压栈
            stk[top++] = cur;
            // 再访问右子树
            cur = cur->right;
        }
    }   
    return array;
}

二叉树的层序遍历

BFS+队列

二叉树的层序遍历，最直接的思路是BFS+队列实现。建立一个队列q，并利用这个队列，按照BFS的遍历方式，完成层序遍历。过程如下：

• 初始化队列，队首front和队尾rear均置为0，根节点入队；同时维护临时变量level，用于记录当前层数。
• 每一层的遍历为一个循环，在遍历开始之前记录队尾下标作为该层遍历结束的标志。在循环中，逐一将该层节点出队，同时把该节点的左孩子和右孩子入队（如果不为NULL的话）。若当前队尾等于遍历开始前记录的队尾下标时，该层遍历结束，层数加一并进入下一次循环。
• 遍历结束的标志为队列为空（q->front == q->rear）。

树的结构定义如下：

 struct TreeNode {
     int val;
     struct TreeNode *left;
     struct TreeNode *right;
 };

再定义数据结构Queue以及初始化、出队和入队操作，作为队列的实现。

// 数据结构Queue定义
typedef struct {
    struct TreeNode* data[2000];
    int front;
    int rear;
} Queue;

// 队列初始化
Queue* initQueue() {
    Queue* q = (Queue*) malloc(sizeof(Queue));
    q->front = 0;
    q->rear = 0;
    return q;
}

// 入队操作：若元素为NULL则不入队
void enQueue(Queue* q, struct TreeNode* x) {
    if (x) {
        q->data[(q->rear)++] = x;
    }
}

// 出队操作：若队列为空则返回NULL
struct TreeNode* deQueue(Queue* q) {
    if (q->front == q->rear) {
        return NULL;
    } else {
        return q->data[(q->front)++];
    }
}

再按照上述思路对二叉树进行层序遍历，代码实现如下：

int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
	/*
		root：二叉树的根节点
		*returnSize：二叉树的层数
		*retrunColumnSizes：二叉树每一层的节点数（int数组）
	*/
	// 为节点数数组分配空间
    int* columnSizes = (int *)malloc(2000 * sizeof(int));
    // 分配一个二维数组空间，用于结果的返回
    int** array = (int**) malloc(2000 * sizeof(int*));
    *returnSize = 0;
    // 若根节点为NULL，直接返回
    if (!root) {
        return array;
    }
    // 记录层数
    int level = 0;
    // 初始化队列
    Queue* q = initQueue();
    // 根节点入队
    enQueue(q, root);
    while (1) {
        // 记录这一层的队尾下标
        int prevRear = q->rear;
        // 计数变量
        int cnt = 0;
        // 为该层的节点分配空间
        array[level] = (int *) malloc((q->rear - q->front) * sizeof(int));
        while (q->front < prevRear) {
            // 节点出队
            struct TreeNode* obj = deQueue(q);
            // 左孩子和右孩子入队
            enQueue(q, obj->left);
            enQueue(q, obj->right);
            // 在结果数组中记录该节点的值
            array[level][cnt++] = obj->val;
        }
        // 记录该层的节点数，且层数+1，准备进入下一次循环
        columnSizes[level++] = cnt;
        // 若队列为空，则遍历结束
        if (q->front == q->rear) {
            break;
        }
    }
    // 记录每层的节点数
    *returnColumnSizes = columnSizes;
    // 记录层数
    *returnSize = level;
    return array;
}

树的遍历还原

给定任意两种树的遍历方式（前序、中序和后序任意两种），可以还原出二叉树的结构。但值得注意的是前序+后序不能唯一确定一棵二叉树，而其他两种组合方式可以。

三种还原的方式思路都是一致的，如下：

• 根据遍历方式的特点确定根节点的位置
• 两种遍历方式组合，找到左子树和右子树的分界位置
• 对左右子树进行递归建树

以前序+中序为例，具体说明此过程：

• 遍历中序遍历数组，找到根节点的下标pivot
• 由pivot计算左子树的长度leftNum = pivot - inLeft
• 根据上述计算，得出左子树的左右边界在前序遍历和中序遍历的下标，将其作为参数传入；右子树同理。

三种二叉树还原代码如下：

前序+中序

struct TreeNode* recurBuild(int* preorder, int* inorder, int preLeft, int preRight, int inLeft, int inRight) {
    if (preLeft > preRight || inLeft > inRight) {
        return NULL;
    }
    int pivot;
    for (pivot = inLeft;pivot <= inRight;pivot++) {
        if (inorder[pivot] == preorder[preLeft]) {
            break;
        }
    }
    int leftNum = pivot - inLeft;
    struct TreeNode* leftTree = recurBuild(preorder, inorder, preLeft + 1, preLeft + leftNum, inLeft, pivot - 1);
    struct TreeNode* rightTree = recurBuild(preorder, inorder, preLeft + leftNum + 1, preRight, pivot + 1, inRight);
    struct TreeNode* root = (struct TreeNode*) malloc(sizeof(struct TreeNode));
    root->val = inorder[pivot];
    root->left = leftTree;
    root->right = rightTree;
    return root;
}

struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){
    return recurBuild(preorder, inorder, 0, preorderSize - 1, 0, inorderSize - 1);
}

后序+中序

struct TreeNode* recurBuild(int* postorder, int* inorder, int postLeft, int postRight, int inLeft, int inRight) {
    if (postLeft > postRight || inLeft > inRight) {
        return NULL;
    }
    int pivot;
    for (pivot = inLeft; pivot <= inRight; pivot++) {
        if (inorder[pivot] == postorder[postRight]) {
            break;
        }
    }
    int rightNum = inRight - pivot;
    struct TreeNode* leftTree = recurBuild(postorder, inorder, postLeft, postRight - rightNum - 1, inLeft, pivot - 1);
    struct TreeNode* rightTree = recurBuild(postorder, inorder, postRight - rightNum, postRight - 1, pivot + 1, inRight);
    struct TreeNode* root = (struct TreeNode*) malloc(sizeof(struct TreeNode));
    root->val = inorder[pivot];
    root->left = leftTree;
    root->right = rightTree;
    return root;
}

struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize){
    return recurBuild(postorder, inorder, 0, postorderSize - 1, 0, inorderSize - 1);
}

前序+后序

前序+后序还原二叉树较为复杂，因为无法通过定位根节点来找到左右子树的长度。因此我们利用前序遍历和后序遍历的特点，找左子树的第一个节点所在的位置，作为上述方法中的pivot，如下图所示：

值得注意的是，若当前子树节点数为1时，需要对此情况进行特判（若仍寻找左子树则会越界）。

struct TreeNode* recurBuild(int* preorder, int* postorder, int preLeft, int preRight, int postLeft, int postRight) {
    if (preLeft > preRight || postLeft > postRight) {
        return NULL;
    }
    // 节点数为1，特判
    if (preLeft == preRight) {
        struct TreeNode* root = (struct TreeNode*) malloc(sizeof(struct TreeNode));
        root->val = preorder[preLeft];
        root->left = NULL;
        root->right = NULL;
        return root;
    }
    int pivot;
    for (pivot = postLeft; pivot <= postRight; pivot++) {
        if (preorder[preLeft + 1] == postorder[pivot]) {
            break;
        }
    }
    int leftNum = pivot - postLeft + 1;
    struct TreeNode* leftTree = recurBuild(preorder, postorder, preLeft + 1, preLeft + leftNum, postLeft, pivot);
    struct TreeNode* rightTree = recurBuild(preorder, postorder, preLeft + leftNum + 1, preRight, pivot + 1, postRight - 1);
    struct TreeNode* root = (struct TreeNode*) malloc(sizeof(struct TreeNode));
    root->val = preorder[preLeft];
    root->left = leftTree;
    root->right = rightTree;
    return root;
}

struct TreeNode* constructFromPrePost(int* preorder, int preorderSize, int* postorder, int postorderSize){
    return recurBuild(preorder, postorder, 0, preorderSize - 1, 0, postorderSize - 1);
}