1, The pre sequence and post sequence of a binary tree are exactly the opposite , Then the binary tree must be ( ) Binary tree of .
answer ： Height is equal to the number of nodes
analysis ： The preorder traversal order is ‘M-L-R’, The sequence of post traversal is ‘L-R-M’, among L-R The relative position of does not change , The change is M Location of . It is pointed out that the results of the first sequence and the second sequence of the binary tree are just the opposite ：
* When a binary tree has only one node , only M,L and R Empty , Meet the conditions
* When the binary tree is empty ,M,L and R All empty , Meet the conditions
* When any node of the binary tree has no left child ,L Empty , Preorder traversal is M-R, Post order traversal is R-M, The result is just the opposite , Meet the conditions
* When any node of the binary tree has no right child ,R Empty , The result of preorder traversal is M-L, The result of post order traversal is L-M, Meet the conditions
* The above four conditions satisfy that the height of the binary tree is equal to the number of nodes
2, The result of preorder traversal of a binary tree is the same as that of middle order traversal , Then all non leaf nodes must meet the following conditions: ?
analysis ： The analysis of this question is similar to the previous one , The answer is only the right subtree
3, The following figure shows a binary tree , Please select the following options that are not sequential sequences generated by traversing a binary tree
answer ：B D
analysis ：
The preorder traversal result is （ root -> Left -> right ）：ABCDEFIGJH
The middle order traversal result is （ Left -> right -> root ）：BDCAIFJGHE
The post order traversal result is （ Left -> right -> root ）：DCBIJHGFEA
4, The preorder traversal of a binary tree is ABCDFGHE, Postorder traversal yes BGHFDECA, Middle order traversal yes ?
answer ：C
analysis ：
* From the preceding sequence （ Root left and right ） First letter and sequence （ Left and right root ） The last letter can know that the root node is A;
*
Middle order （ Zuo Genyou ）, Afterword （ Left and right root ）, The following sequence is B initial , So the middle order should be B start ; Middle order （ Zuo Genyou ）, Antecedent （ Root left and right ）, The preceding sequence is based on E Ending , So the middle order should be E ending , So choose C,B and E The order between is not unique .
* Known preorder traversal and postorder traversal cannot uniquely determine a binary tree . Two trees can be determined according to preorder traversal and postorder traversal ：
So the middle order traversal result is BAGFHDCE That's right .
Technology