二叉树遍历
先序
递归
int *res;
void preorder(struct TreeNode *root, int *returnSize) {
if (root == NULL) return;
// 根左右
res[(*returnSize)++] = root->val;
preorder(root->left, returnSize);
preorder(root->right, returnSize);
}
int *preorderTraversal(struct TreeNode *root, int *returnSize) {
res = (int *) malloc(sizeof(int) * 100);
*returnSize = 0;
preorder(root, returnSize);
return res;
}
迭代
int *preorderTraversal(struct TreeNode *root, int *returnSize) {
int *res = (int *) malloc(sizeof(int) * 100);
*returnSize = 0;
struct TreeNode *stack[100];
int top = 0;
while (top != 0 || root != NULL) {
// 左子树入栈
while (root != NULL) {
// 访问
res[(*returnSize)++] = root->val;
stack[top++] = root;
root = root->left;
}
root = stack[--top];
root = root->right;
}
return res;
}
迭代(右子树先入栈)
int *preorderTraversal(struct TreeNode *root, int *returnSize) {
int *res = (int *) malloc(sizeof(int) * 100);
*returnSize = 0;
if (root == NULL) return res;
struct TreeNode *stack[100];
int top = 0;
stack[top++] = root;
while (top != 0) {
root = stack[--top];
res[(*returnSize)++] = root->val;
// 右子树先入栈
if (root->right != NULL) stack[top++] = root->right;
if (root->left != NULL) stack[top++] = root->left;
}
return res;
}
右左根访问,再反转序列
int *res;
void dfs(struct TreeNode *root, int *returnSize) {
if (root == NULL) return;
// 按右左根的顺序访问,再把序列反过来
dfs(root->right, returnSize);
dfs(root->left, returnSize);
res[(*returnSize)++] = root->val;
}
int *preorderTraversal(struct TreeNode *root, int *returnSize) {
res = (int *) malloc(sizeof(int) * 100);
*returnSize = 0;
if (root == NULL) return res;
dfs(root, returnSize);
// 序列反过来
int left = 0, right = *returnSize - 1;
while (left < right) {
int temp = res[left];
res[left] = res[right];
res[right] = temp;
left++;
right--;
}
return res;
}
Morris
int *res;
// Morris
void preorderMorris(struct TreeNode *root, int *returnSize) {
if (root == NULL) return;
struct TreeNode *cur = root;
while (cur != NULL) {
if (cur->left != NULL) {
// 左子树不空,遍历左子树,找到左子树的最右侧节点
struct TreeNode *rightMost = cur->left;
while (rightMost->right != NULL && rightMost->right != cur) {
rightMost = rightMost->right;
}
// 最右侧节点的右指针指向NULL或者cur
if (rightMost->right == NULL) {
// 有左右孩子的节点第一次被访问
res[(*returnSize)++] = cur->val;
// 把最右侧节点的right指向cur
rightMost->right = cur;
// 访问左子树
cur = cur->left;
} else {
// 有左右孩子的节点第二次被访问
// 恢复
rightMost->right = NULL;
// 遍历右子树
cur = cur->right;
}
} else {
// 只有右孩子的节点只会被访问一次
res[(*returnSize)++] = cur->val;
// 遍历右子树
cur = cur->right;
}
}
}
int *preorderTraversal(struct TreeNode *root, int *returnSize) {
res = (int *) malloc(sizeof(int) * 100);
*returnSize = 0;
if (root == NULL) return res;
preorderMorris(root, returnSize);
return res;
}
中序
递归
int *res;
void inorder(struct TreeNode *root, int *returnSize) {
if (root == NULL) return;
// 左根右
inorder(root->left, returnSize);
res[(*returnSize)++] = root->val;
inorder(root->right, returnSize);
}
int *inorderTraversal(struct TreeNode *root, int *returnSize) {
res = (int *) malloc(sizeof(int) * 100);
*returnSize = 0;
inorder(root, returnSize);
return res;
}
迭代
int *inorderTraversal(struct TreeNode *root, int *returnSize) {
int *res = (int *) malloc(sizeof(int) * 100);
*returnSize = 0;
struct TreeNode *stack[100];
int top = 0;
while (top != 0 || root != NULL) {
// 左子树入栈
while (root != NULL) {
stack[top++] = root;
root = root->left;
}
root = stack[--top];
// 访问
res[(*returnSize)++] = root->val;
root = root->right;
}
return res;
}
Morris
int *res;
void inorderMorris(struct TreeNode *root, int *returnSize) {
if (root == NULL) return;
struct TreeNode *cur = root;
while (cur != NULL) {
if (cur->left != NULL) {
struct TreeNode *rightMost = cur->left;
while (rightMost->right != NULL && rightMost->right != cur) {
rightMost = rightMost->right;
}
if (rightMost->right == NULL) {
rightMost->right = cur;
cur = cur->left;
} else {
// 有左右孩子的节点第二次被经过,左子树都遍历完了,访问节点
res[(*returnSize)++] = cur->val;
rightMost->right = NULL;
cur = cur->right;
}
} else {
// 只有右孩子的节点只会被经过一次,直接访问
res[(*returnSize)++] = cur->val;
cur = cur->right;
}
}
}
int *inorderTraversal(struct TreeNode *root, int *returnSize) {
res = (int *) malloc(sizeof(int) * 100);
*returnSize = 0;
if (root == NULL) return res;
inorderMorris(root, returnSize);
return res;
}
后序
递归
int *res;
void postOrder(struct TreeNode *root, int *returnSize) {
if (root == NULL) return;
// 左右根
postOrder(root->left, returnSize);
postOrder(root->right, returnSize);
res[(*returnSize)++] = root->val;
}
int *postorderTraversal(struct TreeNode *root, int *returnSize) {
res = (int *) malloc(sizeof(int) * 100);
*returnSize = 0;
postOrder(root, returnSize);
return res;
}
迭代
int *postorderTraversal(struct TreeNode *root, int *returnSize) {
int *res = (int *) malloc(sizeof(int) * 100);
*returnSize = 0;
struct TreeNode *stack[100];
int top = 0;
// 记录上个访问的节点
struct TreeNode *pre = NULL;
while (top != 0 || root != NULL) {
// 左子树入栈
while (root != NULL) {
stack[top++] = root;
root = root->left;
}
root = stack[--top];
if (root->right == NULL || root->right == pre) {
// 右子树为空或者已经访问完了,可以访问这个节点了
res[(*returnSize)++] = root->val;
pre = root;
root = NULL;
} else {
// 遍历右子树
// 先把当前节点再次压栈
stack[top++] = root;
root = root->right;
}
}
return res;
}
Morris
int *res;
// 把右子树反转
struct TreeNode *reverseRightTree(struct TreeNode *root) {
struct TreeNode *pre = NULL;
struct TreeNode *cur = root;
while (cur != NULL) {
struct TreeNode *nextRight = cur->right;
cur->right = pre;
pre = cur;
cur = nextRight;
}
return pre;
}
// 自底向上访问右节点(访问反转后的右节点)
void visitReversedRightTree(struct TreeNode *root, int *returnSize) {
// 反转右子树
struct TreeNode *reversed = reverseRightTree(root);
struct TreeNode *cur = reversed;
while (cur != NULL) {
res[(*returnSize)++] = cur->val;
cur = cur->right;
}
// 反转回去
reverseRightTree(reversed);
}
void postorderMorris(struct TreeNode *root, int *returnSize) {
struct TreeNode *cur = root;
while (cur != NULL) {
if (cur->left != NULL) {
struct TreeNode *rightMost = cur->left;
while (rightMost->right != NULL && rightMost->right != cur) {
rightMost = rightMost->right;
}
if (rightMost->right == NULL) {
rightMost->right = cur;
cur = cur->left;
} else {
rightMost->right = NULL;
// 一个节点被第二次经过的时候,自底向上访问左子树的所有的右节点
visitReversedRightTree(cur->left, returnSize);
cur = cur->right;
}
} else {
cur = cur->right;
}
}
// 再遍历一次
visitReversedRightTree(root, returnSize);
}
int *postorderTraversal(struct TreeNode *root, int *returnSize) {
res = (int *) malloc(sizeof(int) * 100);
*returnSize = 0;
if (root == NULL) return res;
postorderMorris(root, returnSize);
return res;
}
层序
int **levelOrder(struct TreeNode *root, int *returnSize, int **returnColumnSizes) {
// 一层最多元素个数
const int size = 1002;
// 最多层数
const int leverMax = 2000;
// 返回的二维数组,第一维表示所在层,第二维表示该层的所有元素
int **res = (int **) malloc(sizeof(int *) * leverMax);
// 一维的维度(多少层)
*returnSize = 0;
// 每个二维的维度(每层多少元素)
*returnColumnSizes = (int *) malloc(sizeof(int) * leverMax);
if (root == NULL) return res;
// 循环队列
struct TreeNode *queue[size];
int lever = 0;
// 保存每层元素个数,下标就是所在层,从0开始
int *columnSize = (int *) calloc(leverMax, sizeof(int));
int front = 0, rear = 0;
queue[rear++] = root;
while (front != rear) {
// 当前层元素数
int count = (rear - front + size) % size;
res[lever] = (int *) malloc(sizeof(int) * count);
int temp = 0;
while (count-- > 0) {
root = queue[(front++) % size];
// 记录当前层的元素
res[lever][temp++] = root->val;
// 当前层元素总数加一
columnSize[lever]++;
if (root->left != NULL) queue[(rear++) % size] = root->left;
if (root->right != NULL) queue[(rear++) % size] = root->right;
}
// 加一层
lever++;
}
*returnSize = lever;
for (int i = 0; i < lever; ++i)
(*returnColumnSizes)[i] = columnSize[i];
return res;
}
标签:遍历,cur,returnSize,int,res,C语言,right,二叉树,root
From: https://www.cnblogs.com/sprinining/p/17937905