Javaでバイナリツリーを再構築する方法

質問: バイナリ ツリーのプリオーダー トラバースとインオーダー トラバースの結果を入力して、バイナリ ツリーを再構築してください。入力された事前順序トラバーサルおよび順序内トラバーサルの結果には、繰り返しの数値が含まれていないと想定されます。たとえば、前順走査シーケンス {1,2,4,7,3,5,6,8} と順走走査シーケンス {4,7,2,1,5,3,8 を入力した場合,6}、次にバイナリ ツリーを再構築して戻ります。

ソリューション分析:

1. 最初のノードの事前順序走査に基づいてルート ノードを決定します。

2. 順序トラバーサルでルート ノードを見つけて、左側のサブツリーの長さと右側のサブツリーの長さを決定します。

3. 長さに応じて、preorder トラバーサルでは左側のサブツリー preorder トラバーサルと右側のサブツリー preorder トラバーサルを取得し、inorder トラバーサルでは左側のサブツリー inorder トラバーサルと右側のサブツリー inorder トラバーサルを取得します。

#4. 左サブツリーと右サブツリーを再帰し、左サブツリー ルート ノードと右サブツリー ルート ノードをルート ノードに割り当てます。

無料のビデオ チュートリアルの推奨事項:

Java 学習

コード:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.*;
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre.length == 0 || in.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(pre[0]);
        for(int i = 0 ; i < in.length; i++) {
            if(in[i] == pre[0]) {
                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i));
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length)
                ,Arrays.copyOfRange(in,i+1,in.length));
            }
        }
        return root;
    }
}

その他の関連記事チュートリアルの推奨事項:

Java プログラミングの概要

以上がJavaでバイナリツリーを再構築する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。