剣指offer 4-再建二叉樹

剣指offer 4-再建二叉樹
最近全国の疫病は深刻で、家にいて用事がなくて、すぐにまた春の募集の準備をして、最近問題をブラシして、記録します!もう一言、武漢は頑張って、みんなは外に出てマスクをすることを覚えています!
1、テーマの説明
ツリーの前順および中順の結果を入力し、ツリーを再構築します.入力された前シーケンスおよび中シーケンスの結果に重複する数値が含まれていないと仮定します.例えば、先行シーケンス遍歴シーケンス{1,2,4,7,3,5,6,8}および中間シーケンス遍歴シーケンス{4,7,2,1,5,3,8,6}を入力すると、ツリーが再構築され、ルートノードが戻されます.
2、構想分析
ツリーの遍歴には、前順遍歴、中順遍歴、後順遍歴の3種類があります.本題は前序と中序遍歴シーケンスに基づいて二叉木を再構築することであり、具体的な例を通じて法則を発見することができ、前序遍歴シーケンスの最初の数字がツリーのルートノードであることを発見することは難しくない.中順ループシーケンスでは、ルートノードの値をスキャンして見つけることができます.左サブツリーのノードはルートノードの左側にあり、右サブツリーのノードはルートノードの右側にあります.このように,この2つのシーケンスにより木のルートノード,左サブツリーノード,右サブツリーノードを見つけ,次に左右サブツリーの構築を再帰的に実現できる.
3、コード

package com.jianzhioffer;
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val=x;
    }
}
public class Main04 {
    private static int index=0;
    private static TreeNode solve(int[] pre,int[] tempIn) {
        int len1=0; //             
        int len2=0; //             
        for(int i=0;i<tempIn.length;i++) {
            if(pre[index]==tempIn[i]) {
                break;
            }
            len1++; //        ++
        }
        len2=tempIn.length-len1-1;
        int index1=0;
        int index2=0;
        int[] tmp1=new int[len1]; //        
        int[] tmp2=new int[len2]; //        
        boolean flag=false;
        for (int i = 0; i < tempIn.length; i++) {
            if(pre[index]==tempIn[i]) {
                flag=true;

            } else if(!flag) {
                tmp1[index1++]=tempIn[i];
            } else {
                tmp2[index2++]=tempIn[i];
            }
        }
        TreeNode node=new TreeNode((pre[index]));
        node.left=null;
        node.right=null;
        if(index<pre.length&& tmp1.length>0) {
            index++;
            node.left=solve(pre,tmp1);

        }
        if(index<pre.length&& tmp2.length>0) {
            index++;
            node.right=solve(pre,tmp2);

        }
        return node;
    }
    public static TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        index=0;//         
        return solve(pre,in);
    }
    public static void main(String[] args) {
        int[] pre={1,2,4,7,3,5,6,8};
        int[] in={4,7,2,1,5,3,8,6};
        TreeNode root=reConstructBinaryTree(pre,in);

        dfs1(root);
        System.out.println();
        dfs2(root);
        System.out.println();

        dfs3(root);
        System.out.println();
    }

    private static void dfs1(TreeNode node) {
        System.out.printf("%d ",node.val);
        if(node.left!=null) {
            dfs1(node.left);
        }
        if(node.right!=null) {
            dfs1(node.right);
        }
    }
    private static void dfs2(TreeNode node) {

        if(node.left!=null) {
            dfs2(node.left);
        }
        System.out.printf("%d ",node.val);
        if(node.right!=null) {
            dfs2(node.right);
        }
    }
    private static void dfs3(TreeNode node) {

        if(node.left!=null) {
            dfs3(node.left);
        }
        if(node.right!=null) {
            dfs3(node.right);
        }
        System.out.printf("%d ",node.val);
    }
}