So first of all, what does the front, middle, and back traversal of a binary tree look like

  • In a front-order traversal, the root node is visited first, then the left child node is visited, and finally the right child node is visited
  • Middle order traversal, left, middle and right
  • Next traverse, left and right center

As you can see, the name is actually based on the order in which the root node is traversed, so the root node is traversed first, the root node is traversed in the middle, and the root node is traversed last.

Because of the characteristics of the traversal mode, it can be known that the first node of the pre-traversal must be the root node, and the last node of the post-traversal must be the root node. In the middle-traversal, the left of the root node is the left subtree, and the right is the right subtree.

The above features are used to reverse the tree by traversing the binary tree’s pre-order and middle-order results.

Here’s the code

import java.util.Objects; /** * @description: * @author: lkb * @create: 2021/8/23 */ public class MyTreeNode { private Object value; private MyTreeNode leftChild; private MyTreeNode rightChild; public MyTreeNode(Object value){ this.value = value; } public MyTreeNode(){@return */ public void buildTree(Object[] preOrderArr, Object[] midOrderArr){ MyTreeNode root = buildTreeCore(new Arr(preOrderArr, 0, preOrderArr.length-1), new Arr(midOrderArr, 0, midOrderArr.length-1)); this.value = root.value; this.leftChild = root.leftChild; this.rightChild= root.rightChild; } private MyTreeNode buildTreeCore(Arr preOrderArr, Arr midOrderArr){ // find root index MyTreeNode rootNode = new MyTreeNode(preOrderArr.getFirstValue()); if((preOrderArr.getStartIndex() == preOrderArr.getEndIndex()) && (midOrderArr.getStartIndex() == midOrderArr.getEndIndex())){ return rootNode; } int rootIndex = midOrderArr.findMatchIndex(rootNode.value); if(rootIndex < 0){ throw new RuntimeException("mid order arr wrong"); } // recurse int leftChildLength = rootIndex - midOrderArr.getStartIndex(); if(leftChildLength > 0){ Arr newPreArr = new Arr(preOrderArr.getArrValue(), preOrderArr.getStartIndex()+1, preOrderArr.getStartIndex() + leftChildLength); Arr newMidArr = new Arr(midOrderArr.getArrValue(), midOrderArr.getStartIndex(), rootIndex-1); rootNode.leftChild = buildTreeCore(newPreArr, newMidArr); } int rightChildLength = midOrderArr.getEndIndex() - rootIndex; if(rightChildLength > 0){ Arr newPreArr = new Arr(preOrderArr.getArrValue(), preOrderArr.getStartIndex()+leftChildLength+1, preOrderArr.getEndIndex()); Arr newMidArr = new Arr(midOrderArr.getArrValue(), rootIndex + 1, midOrderArr.getEndIndex()); rootNode.rightChild = buildTreeCore(newPreArr, newMidArr); } return rootNode; } public static void pre(MyTreeNode rootNode){if(null == rootNode){return;} public static void pre(MyTreeNode rootNode){return; } System.out.print(rootNode.value + "-"); pre(rootNode.leftChild); pre(rootNode.rightChild); } public static void mid(MyTreeNode rootNode){if(null == rootNode){return; } mid(rootNode.leftChild); System.out.print(rootNode.value + "-"); mid(rootNode.rightChild); } @return */ public static void post(MyTreeNode rootNode){if(null == rootNode){return; } post(rootNode.leftChild); post(rootNode.rightChild); System.out.print(rootNode.value + "-"); } class Arr{ private Object[] arrValue; private int startIndex; private int endIndex; public Object[] getArrValue() { return arrValue; } public int getStartIndex() { return startIndex; } public int getEndIndex() { return endIndex; } public Arr(Object[] arrValue, int startIndex, int endIndex){ this.arrValue = arrValue; this.startIndex = startIndex; this.endIndex = endIndex; } @Override public String toString() { StringBuilder stringBuilder = new StringBuilder(); for(int i = startIndex; i<=endIndex; i++){ stringBuilder.append(arrValue[i] ); } return stringBuilder.toString(); } public Object getFirstValue(){ return arrValue[startIndex]; } public int findMatchIndex(Object value){ for(int i=startIndex; i<=endIndex; i++){ if(Objects.equals(arrValue[i], value)){ return i; } } return -1; }}}Copy the code

Here are the test classes

/** * @description: * @author: lkb * @create: Public class Test {public static void main(String[] args) {Integer[] pre = new Integer[]{1,2,4,6,7,3,5}; Integer[] mid = new Integer[]{4,6,7,2,1,5,3}; MyTreeNode myTreeNode = new MyTreeNode(); myTreeNode.buildTree(pre, mid); MyTreeNode.pre(myTreeNode); System.out.println(); MyTreeNode.mid(myTreeNode); System.out.println(); MyTreeNode.post(myTreeNode); System.out.println(); }}Copy the code

The results are as follows