LeetCode Day 2：树

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

 * 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) {
	
    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){
	
	// 分配一段内存，用于存储遍历的节点值
    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;
}

// 该中序遍历方法需要修改树结构
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);
}


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;
}

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;
}