두 갈래 트리 - 전차와 중차 반복 서열 구조 두 갈래 트리
주의: 트리에 중복된 요소가 없다고 가정할 수 있습니다.
예를 들어 앞의 순서 반복preorder=[3,9,20,15,7]의 중간 순서 반복inorder=[9,3,15,20,7]
생각
앞의 순서가 먼저 루트 노드에 접근하기 때문에 앞의 순서가 순서를 반복하는 첫 번째 자모는 틀림없이 루트 노드, 즉 3은 루트 노드이다.그 다음에 중서역은 먼저 왼쪽 트리를 방문하고 뿌리 노드를 방문하고 마지막으로 오른쪽 트리를 방문하기 때문에 우리는 중서역은 중 3의 위치를 찾았다. 그리고 3 왼쪽의 자모는 왼쪽 트리, 즉 9는 뿌리 노드의 왼쪽 트리이다.마찬가지로 15, 20, 7을 뿌리 노드로 하는 오른쪽 나무를 얻는다.
앞의 순서를 9와 15, 20, 7로 나누어 각각 왼쪽 나무와 오른쪽 나무에 똑같은 방법을 적용하여 귀속시키면 두 갈래 나무가 성공적으로 구축된다.다음 그림: 3
/ \
9 20
/ \
15 7
코드 /**
* 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 buildTree(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
}
private TreeNode buildTree(int[] preorder, int[] inorder, int preStart, int preEnd, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) return null;
//
TreeNode root = new TreeNode(preorder[preStart]);
int flag = 0;
// ， flag。
for (int i = inStart; i <= inEnd; i++) {
if (preorder[preStart] == inorder[i]) {
flag = i;
break;
}
}
//
root.left = buildTree(preorder, inorder, preStart + 1, preStart + flag - inStart, inStart, flag - 1);
root.right = buildTree(preorder, inorder, preStart + flag - inStart + 1, preEnd, flag + 1, inEnd);
return root;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSON
JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다.
그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다.
저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
3
/ \
9 20
/ \
15 7
/**
* 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 buildTree(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
}
private TreeNode buildTree(int[] preorder, int[] inorder, int preStart, int preEnd, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) return null;
//
TreeNode root = new TreeNode(preorder[preStart]);
int flag = 0;
// ， flag。
for (int i = inStart; i <= inEnd; i++) {
if (preorder[preStart] == inorder[i]) {
flag = i;
break;
}
}
//
root.left = buildTree(preorder, inorder, preStart + 1, preStart + flag - inStart, inStart, flag - 1);
root.right = buildTree(preorder, inorder, preStart + flag - inStart + 1, preEnd, flag + 1, inEnd);
return root;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
