二叉树的按层打印与ZigZag打印

[编程题]二叉树的按层打印与ZigZag打印

热度指数：1765 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一颗二叉树，分别实现按层和 ZigZag 打印二叉树。

ZigZag遍历: 意思是第一层从左到右遍历，第二层从右到左遍历，依次类推。

输入描述:

第一行输入两个整数 n 和 root，n 表示二叉树的总节点个数，root 表示二叉树的根节点。
以下 n 行每行三个整数 fa，lch，rch，表示 fa 的左儿子为 lch，右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子，rch同理)

输出描述:

先输出按层打印，再输出按ZigZag打印。

示例1

输入

输出

Level 1 : 1
Level 2 : 2 3
Level 3 : 4 5 6
Level 4 : 7 8
Level 1 from left to right: 1
Level 2 from right to left: 3 2
Level 3 from left to right: 4 5 6
Level 4 from right to left: 8 7

备注:

算法知识视频讲解

勇敢牛牛，不怕困难！

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

#define not !

typedef int Id;
const int N = 5E5;

typedef struct {
  Id id;
  Id l_child, r_child;
} TreeNodeInfo, *INFO;

typedef struct TreeNode {
  Id id;
  struct TreeNode* left;
  struct TreeNode* right;
} TreeNode, *PTNode, *BT;

void swap(int* a, int* b) {
  if (a == b) return;
  *a ^= *b, *b ^= *a, *a ^= *b;
}

void reverse(int* arr, const int arrSize) {
  int l = 0, r = arrSize - 1;
  while (l < r) swap(arr + l++, arr + r--);
}


BT CreateBT(INFO infos, Id root_id) {
  // recursion exit condition
  if (!root_id) return NULL;
  
  BT t = (PTNode) malloc(sizeof(TreeNode));
  if (!t) return NULL;
  
  t->id    = root_id;
  t->left  = CreateBT(infos, (*(infos + root_id)).l_child);
  t->right = CreateBT(infos, (*(infos + root_id)).r_child);
  return t;
}

void levelOrder(BT t) {
  // corner case
  if (!t) return;
  
  PTNode q[N];
  int front = 0, rear = 0;
  *(q + rear++) = t;
  
  int level = 1;
  while (front < rear) {
    fprintf(stdout, "Level %d :", level);
    size_t s = rear - front;
    while (s--) {
      t = *(q + front++);
      fprintf(stdout, " %d", t->id);
      if (t->left)  *(q + rear++) = t->left;
      if (t->right) *(q + rear++) = t->right;
    }
    ++level;
    fputc(10, stdout);
  }
}

void levelOrderZigZag(BT t) {
  // corner case
  if (!t) return;
  
  PTNode q[N];
  int front = 0, rear = 0;
  *(q + rear++) = t;
  
  int level = 1;
  int i, vals[(int)1E4], valsSize;
  while (front < rear) {
    printf(level & 1 ? "Level %d from left to right:"
            : "Level %d from right to left:", level);
    
    valsSize = 0;
    size_t s = rear - front;
    while (s--) {
      t = *(q + front++);
      *(vals + valsSize++) = t->id;
      if (t->left)  *(q + rear++) = t->left;
      if (t->right) *(q + rear++) = t->right;
    }
    if (!(level & 1)) reverse(vals, valsSize);
    for (i = 0; i < valsSize; ++i)
      fprintf(stdout, " %d", *(vals + i));
    ++level;
    fputc(10, stdout);
  }
}

int main(const int argc, const char* const argv[]) {
  int n, root_id;
  fscanf(stdin, "%d %d", &n, &root_id);
  
  TreeNodeInfo infos[n + 1];
  Id fa, lch, rch;
  while (n--) {
    fscanf(stdin, "%d %d %d", &fa, &lch, &rch);
    (*(infos + fa)).id = fa;
    (*(infos + fa)).l_child = lch;
    (*(infos + fa)).r_child = rch;
  }
  
  BT t = CreateBT(infos, root_id);
  levelOrder(t);
  levelOrderZigZag(t);
  return 0;
}

发表于 2021-08-03 17:33:55 回复(0)