重建二叉树

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

思路

1557478047042.png

比如上图，A：根节点、B：左节点、C：右节点，前序顺序是ABC（根节点排最先，然后同级先左后右）；中序顺序是BAC(先左后根最后右）；后序顺序是BCA（先左后右最后根）。可以根据前序顺序，得到根节点，然后根据根节点将中序分成两个子树。然后获取从前序获取子树的根节点，依次迭代。

代码

TreeNode.java

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

Solution.java

import java.util.ArrayList;
public class Solution {
    /***
     * 根据前序和中序，重构二叉树
     * @param pre 前序
     * @param in 中序
     * @return 返回头结点
     */
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        TreeNode root=new TreeNode(pre[0]);
        ArrayList<Integer> AIn = new ArrayList<Integer>();
        for (int x =0;x<in.length;x++){
            AIn.add(in[x]);
        }
        ArrayList<Integer> APre = new ArrayList<Integer>();
        for (int x =0;x<in.length;x++){
            APre.add(pre[x]);
        }
//        this.shortPre(root);
        APre.remove(0);
        root=this.Construct(root,APre,AIn);

        return root;
    }

    /***
     * 重构二叉树的循环，划分子树
     * @param root 头结点
     * @param pre 前序
     * @param in 中序
     * @return 头结点
     */
    public TreeNode Construct(TreeNode root,ArrayList<Integer> pre,ArrayList<Integer> in){
        int value = root.val;
        ArrayList<Integer> LIn = new ArrayList<Integer>();
        ArrayList<Integer> RIn = new ArrayList<Integer>();
        boolean state = true;
        for(int x =0;x<in.size();x++){
            if (in.get(x) == value){
                state=false;
            }else{
                if (state){
                    LIn.add(in.get(x));
                }else{
                    RIn.add(in.get(x));
                }
            }
        }
        if(LIn.size()==1){
            TreeNode leftNode=new TreeNode(LIn.get(0));
            root.left=leftNode;
            if(pre.contains(LIn.get(0))){
                pre.remove(LIn.get(0));
            }
        }
        if(LIn.size()>1){
            TreeNode newRoot=new TreeNode(pre.get(0));
            pre.remove(0);
            TreeNode leftNode=this.Construct(newRoot,pre,LIn);
            root.left=leftNode;
        }
        if(RIn.size()==1){
            TreeNode rightNode=new TreeNode(RIn.get(0));
            root.right=rightNode;
            if(pre.contains(RIn.get(0))){
                pre.remove(RIn.get(0));
            }
        }
        if(RIn.size()>1){
            TreeNode newRoot=new TreeNode(pre.get(0));
            pre.remove(0);
            TreeNode rightNode=this.Construct(newRoot,pre,RIn);
            root.right=rightNode;
        }
        return root;
    }

    /***
     * 构建一个树的实例
     * @return 头结点
     */
    public TreeNode create(){
        TreeNode root=new TreeNode(1);
        root.left=new TreeNode(2);
        root.right=new TreeNode(5);
        root.left.right=new TreeNode(3);
        root.right.right=new TreeNode(6);
        root.left.right.left=new TreeNode(4);
        root.right.right.left=new TreeNode(7);
        root.right.right.left.left=new TreeNode(8);
        root.right.right.left.right=new TreeNode(9);
        return root;
    }

    /***
     * 打印前序序列
     * @param root 头结点
     */
    public void  printQian(TreeNode root){
        ArrayList<Integer> result=new ArrayList<Integer>();
        result=this.loopQian(root,result);
        for (int x = 0;x<result.size();x++){
            System.out.print(result.get(x));
            System.out.print(",");
        }

    }

    /***
     * 根据头结点，进行前序遍历的循环体
     * @param root 头结点
     * @param leaf 前序序列
     * @return 前序序列
     */
    public ArrayList<Integer> loopQian(TreeNode root,ArrayList<Integer> leaf){
        leaf.add(root.val);
        if(root.left != null){
            leaf=this.loopQian(root.left,leaf);
        }
        if(root.right != null){
            leaf=this.loopQian(root.right,leaf);
        }
        return leaf;
    }


}