江干区住房和城市建设局网站,北京网页设计有限公司,wordpress微信qq登录,免费动画模板素材网站树的遍历
给定一棵二叉树的后序遍历和中序遍历#xff0c;请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
输入格式#xff1a;
输入第一行给出一个正整数 N ( ≤ 30 ) N(≤30) N(≤30)#xff0c;是二叉树中结点的个数。第二行给出其后序遍历序列。第三…树的遍历
给定一棵二叉树的后序遍历和中序遍历请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
输入格式
输入第一行给出一个正整数 N ( ≤ 30 ) N(≤30) N(≤30)是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。
输出格式
在一行中输出该树的层序遍历的序列。数字间以1个空格分隔行首尾不得有多余空格。
输入样例
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7输出样例
4 1 6 3 5 7 2解题
在后序遍历序列中根节点总是在最后一个位置而在中序遍历序列中根节点将序列分为左右两部分分别对应左子树和右子树。
因此我们可以利用两个数组的信息递归构建二叉树然后再进行层序遍历。
Java
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;// 结点类
class TreeNode {int val; // 值TreeNode left; // 左孩子TreeNode right; // 右孩子TreeNode(int x) {val x;}
}public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int N scanner.nextInt();int[] postOrder new int[N];int[] inOrder new int[N];for (int i 0; i N; i) {postOrder[i] scanner.nextInt();}for (int i 0; i N; i) {inOrder[i] scanner.nextInt();}// 根据后序遍历结果和前序遍历结果构建二叉树TreeNode root helper(postOrder, inOrder);// 层序遍历ListInteger ans levelOrderTraversal(root);// 输出结果for (int i 0; i ans.size(); i) {System.out.print(ans.get(i));if (i ans.size() - 1) {System.out.print( );}}scanner.close();}// 检查是否有某个序列为空private static TreeNode helper(int[] postOrder, int[] inOrder) {if (postOrder null || inOrder null || postOrder.length 0 || inOrder.length 0) {return null;}return buildTree(postOrder, 0, postOrder.length - 1, inOrder, 0, inOrder.length - 1);}/*** 构建二叉树* param postOrder 后序遍历结果* param postStart 后序遍历序列的起始位置* param postEnd 后序遍历序列的结束位置* param inOrder 中序遍历结果* param inStart 中序遍历序列的起始位置* param inEnd 中序遍历序列的结束位置* return 构建的二叉树的根节点*/private static TreeNode buildTree(int[] postOrder, int postStart, int postEnd, int[] inOrder, int inStart, int inEnd) {// (0) 终止条件此时没有结点了返回空树if (postStart postEnd || inStart inEnd) {return null;}// (1) 先找到根结点后序遍历的最后一个结点int rootVal postOrder[postEnd];TreeNode root new TreeNode(rootVal);// (2) 在中序遍历序列中找到根结点的位置int rootIndexInInOrder 0;for (int i inStart; i inEnd; i) {if (inOrder[i] rootVal) {rootIndexInInOrder i;break;}}// (3) 计算左子树的结点个数int leftTreeSize rootIndexInInOrder - inStart;// (4) 递归构建左子树和右子树root.left buildTree(postOrder, postStart, postStart leftTreeSize - 1, inOrder, inStart, rootIndexInInOrder - 1);root.right buildTree(postOrder, postStart leftTreeSize, postEnd - 1, inOrder, rootIndexInInOrder 1, inEnd);// (5) 返回根结点return root;}// 层序遍历二叉树private static ListInteger levelOrderTraversal(TreeNode root) {ListInteger result new ArrayList();if (root null) {return result;}// 创建队列用于层序遍历QueueTreeNode queue new LinkedList();queue.offer(root);// 循环遍历队列中的结点while (!queue.isEmpty()) {TreeNode node queue.poll();// 将当前结点的值加入结果列表result.add(node.val);if (node.left ! null) {queue.offer(node.left); // 将左子结点加入队列}if (node.right ! null) {queue.offer(node.right); // 将右子结点加入队列}}return result;}
}C
#include iostream
#include vector
#include queue
using namespace std;// 结点类
class TreeNode {
public:int val; // 值TreeNode *left; // 左孩子TreeNode *right; // 右孩子TreeNode(int x) {val x;left nullptr;right nullptr;}
};// 构建二叉树
TreeNode* buildTree(vectorint postOrder, int postStart, int postEnd, vectorint inOrder, int inStart, int inEnd) {// 终止条件此时没有结点了返回空树if (postStart postEnd || inStart inEnd) {return nullptr;}// 先找到根结点后序遍历的最后一个结点int rootVal postOrder[postEnd];TreeNode* root new TreeNode(rootVal);// 在中序遍历序列中找到根结点的位置int rootIndexInInOrder 0;for (int i inStart; i inEnd; i) {if (inOrder[i] rootVal) {rootIndexInInOrder i;break;}}// 计算左子树的结点个数int leftTreeSize rootIndexInInOrder - inStart;// 递归构建左子树和右子树root-left buildTree(postOrder, postStart, postStart leftTreeSize - 1, inOrder, inStart, rootIndexInInOrder - 1);root-right buildTree(postOrder, postStart leftTreeSize, postEnd - 1, inOrder, rootIndexInInOrder 1, inEnd);// 返回根结点return root;
}// 层序遍历二叉树
vectorint levelOrderTraversal(TreeNode* root) {vectorint result;if (root nullptr) {return result;}// 创建队列用于层序遍历queueTreeNode* q;q.push(root);// 循环遍历队列中的结点while (!q.empty()) {TreeNode* node q.front();q.pop();// 将当前结点的值加入结果列表result.push_back(node-val);if (node-left ! nullptr) {q.push(node-left); // 将左子结点加入队列}if (node-right ! nullptr) {q.push(node-right); // 将右子结点加入队列}}return result;
}int main() {int N;cin N;vectorint postOrder(N);vectorint inOrder(N);for (int i 0; i N; i) {cin postOrder[i];}for (int i 0; i N; i) {cin inOrder[i];}// 根据后序遍历结果和中序遍历结果构建二叉树TreeNode* root buildTree(postOrder, 0, N - 1, inOrder, 0, N - 1);// 层序遍历vectorint ans levelOrderTraversal(root);// 输出结果for (int i 0; i ans.size(); i) {cout ans[i];if (i ans.size() - 1) {cout ;}}return 0;
}测试链接L2-006 树的遍历
