Reference resources ：
【 data structure 】 Traversing the binary tree

subject

It is known that the preorder traversal order of a binary tree is ABCDEF, The order of traversal is CBAEDF, What is the post order traversal of this tree ？

Answer key

All three traversals start from the root node , Preorder traversal is to print first and then recurse left and right , All preorder traversal sequences are ABCDEF, First letter A It's the root node ; Then traverse the sequence from the middle order CBAEDF, You can know C and B yes A Node on the left subtree of ,E、D、F yes A Node on the right subtree of , We can get the following figure ：

Then look at... In the preceding sequence C and B, First B Again C, therefore B Should be A The left child ,C Just say B My child , as for C yes B Left or right child , Look at the middle order sequence CBAEDF,C stay B Before printing , explain C yes B The left child , Pictured ：

Let's look at the... In the preface E、D、F, Their order is ABCDEF, signify D yes A The right child ,E and F yes D The descendants of （ Be careful , One of them is not necessarily a child , It could also be a grandson ）. Again, the middle order sequence is CBAEDF,E stay D The left side of the ,F On the right side , therefore E yes D The left child ,F yes D The right child , Pictured ：

To avoid derivation errors , We'd better deduce the preorder and inorder traversal sequence again according to this tree . According to the binary tree structure diagram , Easily get the post order traversal as CBEFDA.

summary

Here we can get two properties of traversal of binary tree ：

• We know the preorder traversal sequence and the middle order traversal sequence , You can only identify a binary tree ;
• We know the sequence of post order traversal and the sequence of middle order traversal , You can only identify a binary tree ;

Be careful ： We know preorder and postorder traversal , You can't be sure of a binary tree .