本文共 2840 字，大约阅读时间需要 9 分钟。

根据二叉树的前序遍历和中序遍历构造出二叉树

给出二叉树的前序遍历数组和中序遍历数组构造出该二叉树

例如：

给出整型数组，代表二叉树的前序遍历结果和中序遍历结果，构造出该二叉树。

int[] preorder = {62,15,12,46,35,57,68,65,79};

算法设计

package com.bean.constructbinarytreedemo;import java.util.ArrayList;import java.util.Stack;public class BuildBinaryTreeDemo {    /*     * 二叉树的前序遍历     * */    public static ArrayList
   
     preOrder(TreeNode root){        Stack
    
      stack = new Stack
     
      ();        ArrayList
      
        list = new ArrayList
       
        ();        if(root == null){            return list;        }        stack.push(root);        while(!stack.empty()){            TreeNode node = stack.pop();            list.add(node.data);            if(node.rightChild!=null){                stack.push(node.rightChild);            }            if(node.leftChild != null){                stack.push(node.leftChild);            }        }        System.out.println(list);        return list;    }    /*     * 二叉树的中序遍历     * */    public static ArrayList
        
          inOrder(TreeNode root){ ArrayList
         
           list = new ArrayList
          
           (); Stack
           
             stack = new Stack
            
             (); TreeNode current = root; while(current != null|| !stack.empty()){ while(current != null){ stack.add(current); current = current.leftChild; } current = stack.peek(); stack.pop(); list.add(current.data); current = current.rightChild; } System.out.println(list); return list; } /* * 二叉树的后续遍历 * */ public static ArrayList
             
               postOrder(TreeNode root){ ArrayList
              
                list = new ArrayList
               
                (); if(root == null){ return list; } list.addAll(postOrder(root.leftChild)); list.addAll(postOrder(root.rightChild)); list.add(root.data); System.out.println(list); return list; } //构造二叉树 public TreeNode buildTree(int[] preorder, int[] inorder) { return buildBinaryTreeProcess(0, 0, inorder.length - 1, preorder, inorder); } //构造过程 public TreeNode buildBinaryTreeProcess(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) { if (preStart > preorder.length - 1 || inStart > inEnd) { return null; } TreeNode root = new TreeNode(preorder[preStart]); int inIndex = 0; // Index of current root in inorder for (int i = inStart; i <= inEnd; i++) { if (inorder[i] == root.data) { inIndex = i; } } root.leftChild = buildBinaryTreeProcess(preStart + 1, inStart, inIndex - 1, preorder, inorder); root.rightChild = buildBinaryTreeProcess(preStart + inIndex - inStart + 1, inIndex + 1, inEnd, preorder, inorder); return root; } //测试代码 public static void main(String[] args) { // TODO Auto-generated method stub int[] preorder = { 62,15,12,46,35,57,68,65,79}; int[] inorder = { 12,15,35,46,57,62,65,68,79}; BuildBinaryTreeDemo buildBT=new BuildBinaryTreeDemo(); TreeNode tree = buildBT.buildTree(preorder, inorder); //遍历访问二叉树：前序、中序和后序 buildBT.preOrder(tree); buildBT.inOrder(tree); buildBT.postOrder(tree); }}
               
              
             
            
           
          
         
        
       
      
     
    
   

（完）