검지 Offer Java 섹션 문제 7: 두 갈래 트리 재구성

1536 단어
제목: 두 갈래 나무의 앞 순서와 중간 순서의 결과를 입력하고 이 두 갈래 나무를 재건하십시오.입력한 앞 순서와 중간 순서의 결과에 중복된 숫자가 없다고 가정하십시오.예를 들어 앞 순서 반복 시퀀스 {1,2,4,7,3,5,6,8}와 중간 순서 반복 시퀀스 {4,7,2,1,5,3,8,6}를 입력하면 두 갈래 트리를 재건하고 되돌려줍니다.

연습 주소


https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6

답안을 참고하다

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        if (pre == null || pre.length == 0 || in == null || in.length == 0 || pre.length != in.length) {
            return null;
        }
        return construct(pre, in, 0, pre.length - 1, 0, in.length - 1);
    }
    
    private TreeNode construct(int[] pre, int[] in, int preStart, int preEnd, int inStart, int inEnd) {
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }
        TreeNode node = new TreeNode(pre[preStart]);
        int inMid = inStart;
        while (in[inMid] != pre[preStart]) {
            inMid++;
        }
        int delta = inMid - inStart;
        node.left = construct(pre, in, preStart + 1, preStart + delta, inStart, inMid - 1);
        node.right = construct(pre, in, preStart + delta + 1, preEnd, inMid + 1, inEnd);
        return node;
    }
}

복잡도 분석

  • 시간 복잡도: O(nlogn)..
  • 공간 복잡도: O(n)..

    • 검지 Offer Java 버전 디렉토리 검지 Offer Java 버전 테마
    [검지 Offer 학습] [면접 문제 19: 두 갈래 나무의 거울]
    창고 응용 - 역폴란드식 표현식 값

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage