Leetcode가 알고 있는 전차순(후차순) 전차순과 중차순 전차순 구축 트리
2671 단어 나무.
그리고 앞의 순서(뒤의 순서)를 통해 우리는 뿌리 노드의 위치를 확정한 다음에 뿌리 노드가 중간에서 두루 다니는 위치를 찾아 좌우 트리를 확정할 수 있다.
그리고 좌우 트리로 돌아가 두 갈래 트리를 구축한다.
앞 및 가운데 순서:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder==null&&inorder==null)
return null;
return rebuild (preorder,inorder,0,preorder.length-1,0,inorder.length-1);
}
private TreeNode rebuild(int[] preorder, int[] inorder,int preleft,int preright,int inleft,int inright)
{
if(preleft>preright||inleft>inright)
return null;
TreeNode t=new TreeNode(preorder[preleft]);
t.left=t.right=null;
int loc=0;
//
for (int i=inleft;i<=inright;i++)
if(inorder[i]==preorder[preleft])
{
loc=i;
break;
}
//preleft+1 ,preleft+loc-inleft
t.left=rebuild (preorder,inorder,preleft+1,preleft+loc-inleft,inleft,loc-1);
//preleft+loc-inleft+1 ,preright
t.right=rebuild (preorder,inorder,preleft+loc-inleft+1,preright,loc+1,inright);
return t;
}
}
뒷 순서와 중간 순서:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(inorder==null&&postorder==null)
return null;
return rebuild (inorder,postorder,0,postorder.length-1,0,inorder.length-1);
}
private TreeNode rebuild(int[] in, int[] post,int postleft,int postright,int inleft,int inright)
{
if(postleft>postright||inleft>inright)
return null;
int loc=-1;
TreeNode t=new TreeNode(post[postright]);
t.left=t.right=null;
for (int i=inleft;i<=inright;i++)
if(in[i]==post[postright])
{
loc=i;
break;
}
//postright-inright+loc-1 ,posleft
t.left=rebuild (in,post,postleft,postright-inright+loc-1,inleft,loc-1);
//postright-1 ,postright-inright+loc
t.right=rebuild(in,post,postright-inright+loc,postright-1,loc+1,inright);
return t;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
예제 1.15 UVALive-3902 트리의 검색컨베이어 도어 제목 대의: n대의 기계는 하나의 트리 네트워크로 연결되어 잎 노드는 클라이언트이고 다른 노드는 서버이다. 처음에는 한 대의 서버만 하나의 서비스를 제공했지만 k의 거리 내의 클라이언트만 덮어쓸 수 있...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.