二叉树（根据二叉树的先序遍历和中序遍历构建二叉树）（打印二叉树）

开始

package algorithm;

import java.util.LinkedList;

/**
 * 根据二叉树的先序遍历和中序遍历构建二叉树 参考自[根据前序遍历序列和中序遍历序列重建二叉树]
 * (https://blog.csdn.net/GFJ0814/article/details/52718582)
 * 
 * @author WideStar
 * @version 1.0
 */
public class BuildBinaryTreeV1 {
    class MyTreeNode {
        int val;
        MyTreeNode LeftTree;
        MyTreeNode rightTree;

        public MyTreeNode(int val) {
            // TODO Auto-generated constructor stub
            this.val = val;
        }
    }

    public MyTreeNode reBuildBinaryTree(int[] preOrder, int[] inOrder) {
        if(preOrder.length!=inOrder.length) {
            return null;
        }
        return reBuildBinaryTree(preOrder, 0, preOrder.length - 1, inOrder, 0, inOrder.length - 1);
    }

    public MyTreeNode reBuildBinaryTree(int[] preOrder, int startPre, int endPre, int[] inOrder, int startIn,
            int endIn) {
        MyTreeNode root = new MyTreeNode(preOrder[startPre]);
        // rootPosition表示根节点在中序遍历中的位置
        int rootPosition = findRoot(inOrder, startIn, endIn, preOrder[startPre]);
        if (rootPosition == startIn) {
            root.LeftTree = null;
        } else {
            root.LeftTree = reBuildBinaryTree(preOrder, startPre + 1, startPre + (rootPosition - startIn), inOrder,
                    startIn, rootPosition - 1);
        }
        if (rootPosition == endIn) {
            root.rightTree = null;
        } else {
            root.rightTree = reBuildBinaryTree(preOrder, startPre + (rootPosition - startIn) + 1, endPre, inOrder,
                    rootPosition + 1, endIn);
        }
        return root;
    }

    // 找到根节点在中序遍历数组中的索引
    public int findRoot(int[] inOrder, int startIn, int endIn, int key) {
        for (int i = startIn; i <= endIn; i++) {
            if (inOrder[i] == key) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] preOrder = { 6, 4, 2, 1, 3, 5, 9, 7, 8, 10 };
        int[] inOrder = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        MyTreeNode treeNode = new BuildBinaryTreeV1().reBuildBinaryTree(preOrder, inOrder);
        printBinaryTree(treeNode);
    }

    /*
     * 分层打印二叉树 参考资料 [分层打印二叉树--Java实现]
     * (https://blog.csdn.net/caonuoqi/article/details/71056050)
     */
    public static void printBinaryTree(MyTreeNode root) {
        // 用链表存放节点，采用pop先进先出
        LinkedList<MyTreeNode> queue = new LinkedList<>();
        // 当前行的最右边节点
        MyTreeNode last = root;
        // 下一行打印的最右节点
        MyTreeNode nextLast = null;
        // 存放弹出的节点
        MyTreeNode popNode;
        queue.add(last);
        while (queue.size() > 0) {
            popNode = queue.pop();
            if (popNode.LeftTree != null) {
                nextLast = popNode.LeftTree;
                queue.add(nextLast);
            }
            if (popNode.rightTree != null) {
                nextLast = popNode.rightTree;
                queue.add(nextLast);
            }
            System.out.print("  " + popNode.val);
            if (last == popNode) {
                System.out.println();
                last = nextLast;
            }

        }
    }

}

结束

还可以把循环嵌套的终止条件改为另一种形式,构造树方法如下

public MyTreeNode reBuildBinaryTree(int[] preOrder, int startPre,
            int endPre,int[] inOrder, int startIn, int endIn) {
        if(startIn>endIn) {
            return null;
        }
        MyTreeNode root=new MyTreeNode(preOrder[startPre]);
        //rootPosition表示根节点在中序遍历中的位置
        int rootPosition=findRoot(inOrder, startIn, endIn, preOrder[startPre]);
        root.LeftTree=reBuildBinaryTree(preOrder, startPre+1, startPre+(rootPosition-startIn),
                inOrder, startIn, rootPosition-1);
        root.rightTree=reBuildBinaryTree(preOrder, rootPosition-endIn+endPre+1, endPre,
                inOrder, rootPosition+1, endIn);    
        return root;
    }