二叉树的广度优先遍历
标题:二叉树的广度优先遍历 | 时间限制:1秒 | 内存限制:262144K | 语言限制:不限
有一棵二叉树,每个节点由一个大写字母标识(最多26个节点)。现有两组字母,分别表示后序遍历(左孩子->右孩子->父节点)和中序遍历(左孩子->父节点->右孩子)的结果,请输出层次遍历的结果。
import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { // 构造树的节点 static class TreeNode { char data; TreeNode left; TreeNode right; } //初始化先序遍历数组 static char pre[] = new char[50]; //初始化中序遍历数组 static char in[] = new char[50]; //初始化后序遍历数组 static char post[] = new char[50]; // 本题中是根据中序和后序的遍历来构造 static TreeNode creat(int postL, int postR, int inL, int inR) { // 后序遍历中找到根节点 if (postL > postR) { return null; } TreeNode root = new TreeNode(); root.data = post[postR]; int k = 0; for (int j = inL; j <=inR; j++) { if (in[j] == post[postR]) { k = j; break; } } //中序遍历记录下标记录根节点root在中序遍历中的下标 int cha = k - inL; // 遍历左子树 root.left = creat(postL, postL + cha - 1, inL, k - 1); // 遍历右子树 root.right = creat(postL + cha, postR - 1, k + 1, inR); return root; } // 层次遍历用BFS方法 static void bfs(TreeNode root) { Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.add(root); while (!queue.isEmpty()) { TreeNode v = queue.remove(); System.out.print(v.data); if (v.left != null) { queue.add(v.left); } if (v.right != null) { queue.add(v.right); } } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); String input = sc.nextLine(); String s1 = input.split(" ")[0]; String s2 = input.split(" ")[1]; // 获取输入结点个数 int number = s1.length(); for (int i = 0; i < number; i++) { post[i] = s1.charAt(i); in[i] = s2.charAt(i); } // 建树 TreeNode root = creat(0, number - 1, 0, number - 1); // 层次遍历输出结点data bfs(root); } }
class TreeNode: def __init__(self,value): self.left = None self.right = None self.value = value def TreeFunc(pStr,qStr): if len(pStr) == 0: return None t = TreeNode(pStr[-1]) i = qStr.index(pStr[-1]) qRight = qStr[i+1:] qLeft = qStr[:i] pLeft = pStr[:len(qLeft)] pRight = pStr[len(pLeft):-1] t.right = TreeFunc(pRight, qRight) t.left = TreeFunc(pLeft, qLeft) return t if __name__ == '__main__': inputStr = input().strip() inputList = inputStr.split() pStr = inputList[0] qStr = inputList[1] t = TreeFunc(pStr, qStr) temStr = '' temList = [] temList.append(t) while (len(temList)>0): t = temList[0] temList.pop(0) if (t is not None): temStr += t.value temList.append(t.left) temList.append(t.right) print(temStr)