Java에서 이진 트리를 재구성하는 방법

질문: 이진 트리의 선순 순회 및 순차 순회 결과를 입력하고 이진 트리를 재구성하십시오. 입력된 선순회와 순차순회 결과에 반복되는 숫자가 포함되지 않는다고 가정한다. 예를 들어 선순 순회 시퀀스 {1,2,4,7,3,5,6,8}과 순순 순회 시퀀스 {4,7,2,1,5,3,8을 입력하면 ,6}, 이진 트리를 재구성하고 반환합니다.

솔루션 분석:

1. 첫 번째 노드의 사전 주문 순회를 기반으로 루트 노드를 결정합니다.

2. 순차 순회에서 루트 노드를 찾아 왼쪽 하위 트리의 길이와 오른쪽 하위 트리의 길이를 결정합니다.

3. 길이에 따라 선순 순회에서 왼쪽 하위 트리 선순 순회와 오른쪽 하위 트리 선순 순회를 취하고, 중순 순회에서 오른쪽 하위 트리 순회를 취합니다.

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 중국어 웹사이트의 기타 관련 기사를 참조하세요!