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

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

import java.util.*;

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node (int val) {
        this.val = val;
    }
}

public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Node head = constructTree(sc, n);
        printLevels(head);
        printZigzag(head);
    }
     
    public static Node constructTree (Scanner sc, int n) {
        HashMap<Integer, Node> map = new HashMap<>();
        int rootVal = sc.nextInt();
        Node root = new Node(rootVal);
        map.put(rootVal, root);
        for (int i = 0; i < n; i++) {
            int nodeVal = sc.nextInt();
            int leftVal = sc.nextInt();
            int rightVal = sc.nextInt();
            if (map.containsKey(nodeVal)) {
                Node tmpNode = map.get(nodeVal);
                Node leftNode = leftVal == 0 ? null : new Node(leftVal);
                Node rightNode = rightVal == 0 ? null : new Node(rightVal);
                tmpNode.left = leftNode;
                tmpNode.right = rightNode;
                if (leftVal != 0)
                    map.put(leftVal, leftNode);
                if (rightVal != 0)
                    map.put(rightVal, rightNode);
            }
        }
        return root;
    }
    
    //问题在于何时换行，只需知道何时到了一个level的结尾即可，用两个变量last与nlast记录
    //本行结尾与下一行结尾，每次让last = nlast。而nlast则一直跟踪记录宽度优先的队列中
    //新加入的数即可。
    public static void printLevels(Node head) {
        if (head == null) {
            return;
        }
        Node last = head;
        Node nlast = null;
        Queue<Node> q = new LinkedList<Node>();
        q.offer(head);
        int level = 1;
        System.out.print("Level " + (level++) + " : ");
        while (!q.isEmpty()) {
            Node cur = q.poll();
            System.out.print(cur.val + " ");
            if (cur.left != null) {
                q.offer(cur.left);
                nlast = cur.left;
            }
            if (cur.right != null) {
                q.offer(cur.right);
                nlast = cur.right;
            }
            if (cur == last && !q.isEmpty()) {
                System.out.println();
                System.out.print("Level " + (level++) + " : ");
                last = nlast;
            }
        }
        System.out.println();
    }
    
    public static void printZigzag (Node head) {
        if (head == null)
            return;
        Node cur = head;
        Node last = head;
        Node nlast = null;
        Deque<Node> dq = new LinkedList<Node>();
        dq.offerFirst(cur);
        int level = 1;
        boolean fLtR = true;
        System.out.print("Level " + (level++) + " from left to right: " );
        while (!dq.isEmpty()) {
            if (fLtR) {
                head = dq.pollFirst();
                if (head.left != null) {
                    dq.offerLast(head.left);
                    nlast = nlast == null ? head.left : nlast;
                }
                if (head.right != null) {
                    dq.offerLast(head.right);
                    nlast = nlast == null ? head.right : nlast;
                }
            }
            else {
                head = dq.pollLast();
                if (head.right != null) {
                    dq.offerFirst(head.right);
                    nlast = nlast == null ? head.right : nlast;
                }
                if (head.left != null) {
                    dq.offerFirst(head.left);
                    nlast = nlast == null ? head.left : nlast;
                }
            }
            System.out.print(head.val + " ");
            if (last == head && !dq.isEmpty()) {
                System.out.println();
                fLtR = !fLtR;
                if (fLtR)
                    System.out.print("Level " + (level++) + " from left to right: " );
                else
                    System.out.print("Level " + (level++) + " from right to left: " );
                last = nlast;
                nlast = null;
            }
        }
        System.out.println();
    }
}

class TreeNode:
    def __init__(self,x):
        self.val = x
        self.left = None
        self.right = None

def PrintFromTopToBottom(root):
    # write code here
    if not root:
        return []
    queue = [root]
    res = []
    while len(queue)>0:
        # 当前队列的大小为每层节点的个数
        level_size = len(queue)
        temp = []
        for _ in range(level_size):
            top = queue.pop(0)
            temp.append(top.val)
            if top.left:
                queue.append(top.left)
            if top.right:
                queue.append(top.right)
        res.append(temp)
    return res

def PrintZigZag(root):
    if not root:
        return []
    queue = [root]
    count = 0  # 标志位，判断当前是奇数还是偶数层
    res = []
    while len(queue):
        # 当前队列的大小为每层节点的个数
        level_size = len(queue)
        count += 1
        stack = []
        temp = []
        for _ in range(level_size):

            if count % 2 != 0:
                d = queue.pop(0)

                temp.append(d.val)

                if d.left:
                        queue.append(d.left)
                if d.right:
                        queue.append(d.right)
            else: # 对偶数层进行处理
                d = queue.pop()

                temp.append(d.val)
                stack.append(d)

                if len(stack) == level_size:
                    for _ in range(level_size):
                        q = stack.pop()
                        if q.left:
                            queue.append(q.left)
                        if q.right:
                            queue.append(q.right)
        res.append(temp)
    return res

if __name__ == "__main__":
    # a是二叉树节点个数，b是二叉树的根节点值
    n, r = map(int, input().split())
    root = TreeNode(r)
    nodes = {r: root}
    for _ in range(n):
        v, l, r = map(int, input().split())
        if l!= 0:
            nodes[l] = TreeNode(l)
            nodes[v].left = nodes[l]
        if r != 0:
            nodes[r] = TreeNode(r)
            nodes[v].right = nodes[r]
    # 按层打印
    res1 = PrintFromTopToBottom(root)
    #按ZigZag打印
    res2 = PrintZigZag(root)
    for i,r in enumerate(res1):
         print("Level {} : {}".format(i+1," ".join(str(x) for x in res1[i])))
    for i,r in enumerate(res2):
        if i%2==0:
            print("Level {} from left to right: {}".format(i+1, " ".join(str(x) for x in res2[i])))
        else:
            print("Level {} from right to left: {}".format(i+1, " ".join(str(x) for x in res2[i])))

好醉好醉，两次没通过竟然是因为和标准输出的空格对不上！！！

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void printByLevel(Node root) {
        if (root == null) {
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        int level = 1;
        Node last = root;
        Node nlast = null;
        System.out.print("Level " + level++ + " : ");
        while (!queue.isEmpty()) {
            root = queue.poll();
            System.out.print(root.value + " ");
            if (root.left != null) {
                queue.offer(root.left);
                nlast = root.left;
            }
            if (root.right != null) {
                queue.offer(root.right);
                nlast = root.right;
            }
            if (root == last && !queue.isEmpty()) {
                System.out.println();
                System.out.print("Level " + level++ +" : ");
                last = nlast;
            }
        }
    }

    public static void printZigZag(Node root) {
        if (root == null) {
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        int level = 1;
        Node last = root;
        Node nlast = null;
        boolean judge = false;
        ArrayList<Node> arrayList = new ArrayList<>();
        System.out.print("Level " + level++ + " from left to right : ");
        while (!queue.isEmpty()) {
            root = queue.poll();
            arrayList.add(root);
            if (root.left != null) {
                queue.offer(root.left);
                nlast = root.left;
            }
            if (root.right != null) {
                queue.offer(root.right);
                nlast = root.right;
            }
            if (root == last && !queue.isEmpty()) {
                if (judge) {
                    for (int i = arrayList.size() - 1; i >= 0; i--) {
                        System.out.print(arrayList.get(i).value + " ");
                    }
                } else {
                    for (int i = 0; i <= arrayList.size() - 1; i++) {
                        System.out.print(arrayList.get(i).value + " ");
                    }
                }
                arrayList.clear();
                judge = !judge;
                System.out.println();
                if (judge) {
                    System.out.print("Level " + level++ + " from right to left : ");
                } else {
                    System.out.print("Level " + level++ + " from left to right : ");
                }
                last = nlast;
            }
        }
        if (judge) {
            for (int i = arrayList.size() - 1; i >= 0; i--) {
                System.out.print(arrayList.get(i).value + " ");
            }
        } else {
            for (int i = 0; i <= arrayList.size() - 1; i++) {
                System.out.print(arrayList.get(i).value + " ");
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strings = br.readLine().split(" ");
        int n = Integer.parseInt(strings[0]);
        int root = Integer.parseInt(strings[1]);
        Node head1 = new Node(root);
        int[][] arr1 = new int[n + 1][2];
        for (int i = 0; i < n; i++) {
            strings = br.readLine().split(" ");
            arr1[Integer.parseInt(strings[0])][0] = Integer.parseInt(strings[1]);
            arr1[Integer.parseInt(strings[0])][1] = Integer.parseInt(strings[2]);
        }
        createTree(head1, arr1);
        printByLevel(head1);
        System.out.println();
        printZigZag(head1);
    }

    public static void createTree(Node head, int[][] arr) {
        if (head == null) {
            return;
        }
        if (arr[head.value][0] != 0) {
            head.left = new Node(arr[head.value][0]);
            createTree(head.left, arr);
        }
        if (arr[head.value][1] != 0) {
            head.right = new Node(arr[head.value][1]);
            createTree(head.right, arr);
        }
    }
}


class Node {
    public int value;
    public Node left;
    public Node right;

    public Node(int data) {
        this.value = data;
    }
}

#include<bits/stdc++.h>
using namespace std;
void printByLevel(int root,int* lc,int* rc)
{
    if(!root) return;
    deque<int>q;
    q.push_back(root);
    int level = 1;
    while(!q.empty())
    {
        int len = q.size();
        cout<<"Level "<<level<<" :";
        for(int i=0;i<len;++i)
        {
            int cur = q.front();
            q.pop_front();
            cout<<" "<<cur;
            if(lc[cur]) q.push_back(lc[cur]);
            if(rc[cur]) q.push_back(rc[cur]);
        }
        cout<<endl;
        ++level;
    }
}
void printByZigZag(int root,int* lc,int* rc)
{
    if(!root) return;
    deque<int>q;
    int level = 1;
    q.push_back(root);
    while(!q.empty())
    {
        if(level&1)
        {
            cout<<"Level "<<level<<" from left to right:";
            int len = q.size();
            for(int i=0;i<len;++i)
            {
                int cur = q.front();
                q.pop_front();
                cout<<" "<<cur;
                if(lc[cur]) q.push_back(lc[cur]);
                if(rc[cur]) q.push_back(rc[cur]);
            }

        }
        else{
            cout<<"Level "<<level<<" from right to left:";
            int len = q.size();
            for(int i=0;i<len;++i)
            {
                int cur = q.back();
                q.pop_back();
                cout<<" "<<cur;
                if(rc[cur]) q.push_front(rc[cur]);
                if(lc[cur]) q.push_front(lc[cur]);
            }
        }
        cout<<endl;
        ++level;
    }

}
int main()
{
    int n,root;
    cin>>n>>root;
    int p;
    int* lc = new int[n+1];
    int* rc = new int[n+1];
    for(int i=0;i<n;++i)
    {
        cin>>p;
        cin>>lc[p]>>rc[p];
    }
    printByLevel(root,lc,rc);
    printByZigZag(root,lc,rc);
    return 0;
}