给定一颗二叉树,分别实现按层和 ZigZag 打印二叉树。
ZigZag遍历: 意思是第一层从左到右遍历,第二层从右到左遍历,依次类推。
第一行输入两个整数 n 和 root,n 表示二叉树的总节点个数,root 表示二叉树的根节点。
以下 n 行每行三个整数 fa,lch,rch,表示 fa 的左儿子为 lch,右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子,rch同理)
先输出按层打印,再输出按ZigZag打印。
8 1 1 2 3 2 4 0 4 0 0 3 5 6 5 7 8 6 0 0 7 0 0 8 0 0
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
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.HashMap; import java.util.Queue; import java.util.LinkedList; class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int val) { this.val = val; } } public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 构建二叉树 String[] params = br.readLine().split(" "); int n = Integer.parseInt(params[0]); TreeNode root = new TreeNode(Integer.parseInt(params[1])); HashMap<Integer, TreeNode> map = new HashMap<>(); map.put(root.val, root); for(int i = 0; i < n; i++){ params = br.readLine().split(" "); int val = Integer.parseInt(params[0]); int leftVal = Integer.parseInt(params[1]); int rightVal = Integer.parseInt(params[2]); TreeNode node = map.get(val); if(leftVal != 0) { node.left = new TreeNode(leftVal); map.put(leftVal, node.left); } if(rightVal != 0) { node.right = new TreeNode(rightVal); map.put(rightVal, node.right); } } // 层次遍历 Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int level = 1; while(!queue.isEmpty()){ int queueSize = queue.size(); System.out.print("Level " + level + " : "); for(int i = 0; i < queueSize; i++){ TreeNode node = queue.poll(); System.out.print(node.val + " "); if(node.left != null) queue.offer(node.left); if(node.right != null) queue.offer(node.right); } System.out.println(); level ++; } // ZigZag层次遍历 queue.offer(root); level = 1; while(!queue.isEmpty()){ int queueSize = queue.size(); if(level % 2 == 1){ System.out.print("Level " + level + " from left to right: "); for(int i = 0; i < queueSize; i++){ TreeNode node = queue.poll(); System.out.print(node.val + " "); if(node.left != null) queue.offer(node.left); if(node.right != null) queue.offer(node.right); } }else{ System.out.print("Level " + level + " from right to left: "); String[] layer = new String[queueSize]; for(int i = 0; i < queueSize; i++){ TreeNode node = queue.poll(); layer[i] = String.valueOf(node.val); if(node.left != null) queue.offer(node.left); if(node.right != null) queue.offer(node.right); } for(int i = queueSize - 1; i >= 0; i--) System.out.print(layer[i] + " "); } level ++; System.out.println(); } } }
#include <iostream> #include <vector> #include <algorithm> #include <queue> using namespace std; int v[500001][2]; void Level(int root){ queue<int>que; que.push(root); int level = 1; while(!que.empty()){ int size = que.size(); cout<<"Level " <<level<<" : "; for(int i = 0;i<size;++i){ int top = que.front(); que.pop(); cout<<top<<" "; if(v[top][0]){ que.push(v[top][0]); } if(v[top][1]){ que.push(v[top][1]); } } ++level; cout<<endl; }// while } void ZigZag(int root){ queue<int>q; q.push(root); int flag = 1; int level = 1; while(!q.empty()){ if(flag == 1){ cout<<"Level "<<level<<" from"<<" left"<<" to"<<" right: "; }else{ cout<<"Level "<<level<<" from"<<" right"<<" to"<<" left: "; } vector<int>temp; int size = q.size(); for(int i = 0;i<size;++i){ int top = q.front(); q.pop(); temp.push_back(top); if(v[top][0]){ q.push(v[top][0]); } if(v[top][1]){ q.push(v[top][1]); } } if(flag == 1){ for(int i = 0;i<temp.size();++i){ cout<<temp[i]<<" "; } cout<<endl; }else{ for(int i = temp.size()-1;i>=0;--i){ cout<<temp[i]<<" "; } cout<<endl; } ++level; flag *= -1; } } int main(){ int n,root; cin>>n>>root; for(int i = 0;i<n;++i){ int p; cin>>p; cin>>v[p][0]; cin>>v[p][1]; } Level(root); ZigZag(root); return 0; }
#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])))运行超时:您的程序未能在规定时间内运行结束,请检查是否循环有错或算法复杂度过大。75%通过。该怎么改进?
好醉好醉,两次没通过竟然是因为和标准输出的空格对不上!!! 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; }