검지offer---이차수 재건
제목은 어떤 두 갈래 나무의 앞 순서와 중간 순서의 결과를 입력하고 이 두 갈래 나무를 재건하십시오.입력한 앞 순서와 중간 순서의 결과에 중복된 숫자가 없다고 가정하십시오.예를 들어 앞 순서 반복 시퀀스 {1,2,4,7,3,5,6,8}와 중간 순서 반복 시퀀스 {4,7,2,1,5,3,8,6}를 입력하면 두 갈래 트리를 재건하고 되돌려줍니다.
/**
* 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) {
return fun(pre, in, 0, pre.length,0 ,in.length -1 );
}
private TreeNode fun(int[] pre, int[] in, int preLeftIndex,int preRightIndex, int inLeftIndex, int inRightIndex){
if(inLeftIndex > inRightIndex || preLeftIndex > preRightIndex){
return null;
}
TreeNode root = new TreeNode(pre[preLeftIndex]);
for(int i = inLeftIndex; i <= inRightIndex; i++){
if(in[i] == pre[preLeftIndex]){
root.left = fun(pre, in, preLeftIndex + 1, preLeftIndex + i - inLeftIndex, inLeftIndex, i - 1 );
root.right = fun(pre, in, preLeftIndex + i - inLeftIndex + 1, preRightIndex,i + 1, inRightIndex);
break;
}
}
return root;
}
}
생각:
두 갈래 나무의 앞 순서와 중간 순서
그래서 전차 역행의 특징은 전차 역행의 모든 노드는 현재 자나무의 뿌리 노드이다. 또한 중차 역행 중의 이 노드를 경계로 하여 중차 역행의 결과를 왼쪽 자나무와 오른쪽 자나무로 나눌 수 있다.
앞의 첫 번째 노드는 중간 노드의 결과를 {4,7,2}와 {5,3,8,6} 두 부분으로 나눈다. 그는 1을 뿌리로 하는 좌우 두 개의 자목의 모든 노드를 이어서 그 자목을 상술한 방법에 따라 나누면 원시적인 나무 구조를 얻을 수 있다.참고: 이 해법은 트리에 반복 노드의 몇 가지 주의해야 할 점이 없음을 보증합니다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
