검지offer 알고리즘---전차 역과 중차 역과에 따라 두 갈래 트리 재생성
1298 단어 검지offer 알고리즘
모래를 쌓아 탑을 이루다.
제목 설명: 두 갈래 나무의 앞 순서와 중간 순서의 결과를 입력하고 이 두 갈래 나무를 다시 만드십시오.입력한 앞 순서와 중간 순서의 결과에 중복된 숫자가 없다고 가정하십시오.예를 들어 앞 순서 반복 시퀀스 {1,2,4,7,3,5,6,8}와 중간 순서 반복 시퀀스 {4,7,2,1,5,3,8,6}를 입력하면 두 갈래 트리를 재건하고 되돌려줍니다.
알고리즘 분석:
전차적 역주행과 중차적 역주행에 따라 두 갈래 나무를 생성하는 상황에서 먼저 전차적 역주행을 통해 뿌리를 얻은 다음에 중차적 역주행에 따라 좌우 나무의 원소를 얻고 같은 사고방식에 따라 계속 좌우 나무를 생성한다.위에서 볼 수 있듯이 이것은 귀속의 과정이기 때문에 실현 사고방식은 좌우 자수를 확정하는 전제에서 귀속하여 자수를 만드는 것이다.
구현 코드:
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class CreatTree {
public TreeNode reConstructBinaryTree(int [] pre, int [] in) {
if(pre.length==1)
return new TreeNode(pre[0]);
if(pre.length==0)
return null;
int index=0;
TreeNode gen=new TreeNode(pre[0]);
while(in[index]!=pre[0])
index++;//
int[] inLeft=new int[index];//
int[] preLeft=new int[index];//
for(int i=0;i이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
검지offer 시리즈: 두 갈래 검색 트리의 뒷순서 반복 시퀀스정수 그룹을 입력하여 이 그룹이 어떤 두 갈래 검색 트리의 후순으로 옮겨다니는 결과인지 판단하십시오.예이면 Yes를 내보내고 그렇지 않으면 No를 내보냅니다.입력한 그룹의 임의의 두 숫자가 서로 다르다고 가정하십시오...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
