Shulou(Shulou.com)06/01 Report--

It is believed that many inexperienced people have no idea about the java algorithm of finding the second order in the pre-order. therefore, this paper summarizes the causes and solutions of the problem. Through this article, I hope you can solve this problem.

The definition of preorder, middle order and post-order traversal of binary tree: preorder traversal: for any subtree, first visit the follower, then traverse its left subtree, and finally traverse its right subtree; mid-order traversal: for any subtree, first traverse its left subtree, then access the root, and finally traverse its right subtree; post-order traversal: for any subtree, first traverse its left subtree, then traverse its right subtree, and finally visit the root. Given the pre-order traversal and mid-order traversal of a binary tree, find its post-order traversal (hint: given pre-order traversal and mid-order traversal can only determine the post-order traversal). Variable condition: the name of the node in the binary tree is expressed in uppercase letters: a _ 26 nodes at most. Running time limit: 1 second / test data. Input format: two lines, the first behavior pre-order traversal, the second behavior order traversal. Output format: if you can not get the post-order traversal according to the pre-order and mid-order traversal, output NO ANSWER;, otherwise output a line, for post-order traversal. / * * preorder traversal: GDAFEMHZ * preorder traversal: ADEFGHMZ * two steps:  constructs a binary tree  post-order traversal binary tree according to the preorder middle order * according to the characteristics of preorder traversal, the root node is G * root node to divide the middle order traversal result ADEFGHMZ into ADEF and HMZ left subtrees and right subtrees. * Recursively determine the subtree structure of the middle order traversal sequence ADEF and the preorder traversal sequence DAFE; * Recursively determine the subtree structure of the middle order traversal sequence HMZ and the preorder traversal sequence MHZ; * / public class PostOrder {public static void main (String [] args) throws Exception {/ / Scanner in = new Scanner (System.in); / / String pre,mid / / while (in.hasNext ()) {/ / pre = in.next (); / / mid = in.next (); / / System.out.println (postOrder (pre,mid)); / /} String pre = "ABDGCEFH"; String mid = "DGBAECHF"; System.out.println (postOrder (pre,mid)) } private static String postOrder (String pre, String mid) throws Exception {if (pre.length () = = 1) return pre; else if (pre.length () = = 0) return ""; int m = mid.indexOf (pre.charAt (0)) Return postOrder (pre.substring (1 ~ m), mid.substring (0, m) + postOrder (pre.substring (m ~ 1), mid.substring (m ~ 1)) + pre.charAt (0) }} / * * * in order traversal: ADEFGHMZ * post order traversal: AEFDHZMG * the last node is the root node, that is, the root node is G * / public class PreOrder {public static void main (String [] args) throws Exception {String post = "AEFDHZMG"; String mid = "ADEFGHMZ"; System.out.println (preOrder (post,mid)) } private static String preOrder (String post, String mid) throws Exception {if (post.length () = = 1) return post; else if (post.length () = = 0) return ""; int m = mid.indexOf (post.charAt (post.length ()-1)) Return post.charAt (post.length ()-1) + preOrder (post.substring (post.length ()-mid.length (), m), mid.substring (0Magnem)) + preOrder (post.substring (mjournal post.length ()-1), mid.substring (mendic1));}} after reading the above, have you mastered the java algorithm for finding the post order in the preorder? If you want to learn more skills or want to know more about it, you are welcome to follow the industry information channel, thank you for reading!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.