나무: 두 갈래 나무 재건
제목 설명
두 갈래 나무의 앞 순서와 중간 순서의 결과를 입력하십시오. 이 두 갈래 나무를 다시 만드십시오.입력한 앞 순서와 중간 순서의 결과에 중복된 숫자가 없다고 가정하십시오.예를 들어 앞 순서 반복 시퀀스 {1,2,4,7,3,5,6,8}와 중간 순서 반복 시퀀스 {4,7,2,1,5,3,8,6}를 입력하면 두 갈래 트리를 재건하고 되돌려줍니다.
/// 1
/// / \
/// 2 3
/// / / \
/// 4 5 6
/// \ /
/// 7 8 문제 풀이 사고방식
기초 지식
앞의 순서 반복: 뿌리 결점 ---> 왼쪽 트리 ---> 오른쪽 트리 중 순서 반복: 왼쪽 트리 ---> 뿌리 결점 ---> 오른쪽 트리 뒤의 순서 반복: 왼쪽 트리 ---> 오른쪽 트리 ---> 뿌리 결점 순서 반복: 순서대로 반복만 하면 된다
예:
전차 역력: 1 2 4 7 3 5 6 8 중차 역력: 4 7 2 1 5 3 8 6 후차 역력: 7 4 2 5 8 6 3 1 차원 역력: 1 2 3 4 5 6 7 8
앞의 순서는 먼저 뿌리 결점을 방문한 다음에 왼쪽 트리를 훑어보고 마지막으로 오른쪽 트리를 훑어본다.왼쪽, 오른쪽 나무를 훑어볼 때, 뿌리 결점을 먼저 방문한 다음, 왼쪽 나무를 훑어보고, 마지막에 오른쪽 나무를 훑어본다.LDR은 두 갈래 나무가 두루 다니는 일종으로 중근 두루 다니기, 중서 두루 다니기라고도 부른다.두 갈래 나무에서 중서는 먼저 왼쪽 나무를 훑어본 다음에 뿌리 결점을 방문하고 마지막으로 오른쪽 나무를 훑어본다.두 갈래 나무의 어떤 역력은 사실 기억하기 쉽다. 바로 뿌리가 있는 것이냐, 바로 어떤 역력이냐. 앞에서는 앞역력, 가운데는 중역력, 뒤에는 후역력, 다른 것은 차원역력이다.
문제 풀기:
앞 순서에 따라 뿌리 노드(1)를 알 수 있고, 중간 순서에 따라 왼쪽 나무(4,7,2)와 오른쪽 나무(5,3,8,6)를 알 수 있다.좌우 나무를 찾은 후에 우리는 같은 방식으로 좌우 나무를 찾을 수 있다. 즉, 이것은 귀속적인 과정이다.루트 > 왼쪽 > 오른쪽.
코드 구현
두 갈래 나무
////// /// public class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int x) { val = x; } }
前序遍历：根结点 ---> 左子树 ---> 右子树
public static void PreNode(TreeNode node, List<int> treeList)
{
if (node != null)
{
treeList.Add(node.val);
PreNode(node.left, treeList);
PreNode(node.right, treeList);
}
}중차순 반복: 왼쪽 트리 ---> 루트 결점 ---> 오른쪽 트리
public static void MidNode(TreeNode node, List<int> treeList)
{
if (node != null) {
MidNode(node.left, treeList);
treeList.Add(node.val);
MidNode(node.right, treeList);
}
}후순 반복: 왼쪽 트리 ---> 오른쪽 트리 ---> 루트 결점
public static void EndNode(TreeNode node, List<int> treeList)
{
if (node != null) {
EndNode(node.left, treeList);
EndNode(node.right, treeList);
treeList.Add(node.val);
}
}차원 이동: 차원 이동만 하면 된다.사고방식: 차원 반복의 순서에 따라 각 층은 왼쪽에서 오른쪽으로 반복 출력되고 하나의 대열을 빌린다.먼저 루트 노드에서 대열에 들어가 현재 노드의 왼쪽 노드가 빈 왼쪽 노드가 아닌 경우, 현재 오른쪽 노드 부위가 빈 오른쪽 노드가 대열에 있는 경우.그래서 출대 순서는 왼쪽에서 오른쪽이다.
public static void LevelNode(TreeNode node, List<int> treeList)
{
if (node != null) {
Queue queue = new Queue();
queue.Enqueue(node);
TreeNode currentNode = null;
while (queue.Count > 0) {
currentNode = queue.Dequeue();
treeList.Add(currentNode.val);
if (currentNode.left != null) {
queue.Enqueue(currentNode.left);
}
if (currentNode.right != null) {
queue.Enqueue(currentNode.right);
}
}
}
} 두 갈래 나무의 전차 역주행과 중차 역주행 결과는 이 두 갈래 나무를 재건해 주십시오.사고방식: 앞의 순서에 따라 뿌리를 찾고, 중간의 순서에 따라 좌우 나무를 찾고, 순서대로 귀속한다.귀결: 루트 > 왼쪽 > 오른쪽
public static TreeNode Tree(List<int> preTree, List<int> midTree)
{
if (preTree == null || preTree.Count() == 0 || midTree == null || midTree.Count() == 0)
{
return null;
}
//
int rootTree = preTree[0];
//
preTree.RemoveAt(0);
TreeNode treeNode = new TreeNode(rootTree);
//
List<int> leftTree = null;
List<int> tempList = new List<int>();
bool isTree = false;
foreach (var item in midTree)
{
tempList.Add(item);
if (item == rootTree)
{
isTree = true;
tempList.Remove(item);
leftTree = tempList;
tempList = new List<int>();
}
}
if (!isTree) {
Console.WriteLine(" ");
return null;
}
List<int> rightTree = tempList;
//
treeNode.left = Tree(preTree, leftTree);
treeNode.right = Tree(preTree, rightTree);
return treeNode;
}테스트
일반 두 갈래 나무
///
///
/// 1
/// / \
/// 2 3
/// / / \
/// 4 5 6
/// \ /
/// 7 8
///
[Fact]
public void Common() {
int[] preTree = { 1, 2, 4, 7, 3, 5, 6, 8 };
int[] midTree = { 4, 7, 2, 1, 5, 3, 8, 6 };
TreeNode tree = Coding004.Tree(preTree.ToList(), midTree.ToList());
List<int> result = new List<int>();
Coding004.PreNode(tree, result);
Assert.Equal(JsonConvert.SerializeObject(preTree), JsonConvert.SerializeObject(result));
result.Clear();
Coding004.MidNode(tree, result);
Assert.Equal(JsonConvert.SerializeObject(midTree), JsonConvert.SerializeObject(result));
} 모든 결점은 오른쪽 결점이 없다
///
///
/// 1
/// /
/// 2
/// /
/// 3
///
[Fact]
public void Right()
{
int[] preTree = { 1, 2, 3 };
int[] midTree = { 3, 2, 1 };
TreeNode tree = Coding004.Tree(preTree.ToList(), midTree.ToList());
List<int> result = new List<int>();
Coding004.PreNode(tree, result);
Assert.Equal(JsonConvert.SerializeObject(preTree), JsonConvert.SerializeObject(result));
result.Clear();
Coding004.MidNode(tree, result);
Assert.Equal(JsonConvert.SerializeObject(midTree), JsonConvert.SerializeObject(result));
} 모든 결점은 왼쪽 결점이 없다
///
///
/// 1
/// \
/// 2
/// \
/// 3
/// \
///
/// \
/// 5
///
[Fact]
public void Left()
{
int[] preTree = { 1, 2, 3, 4, 5 };
int[] midTree = { 1, 2, 3, 4, 5 };
TreeNode tree = Coding004.Tree(preTree.ToList(), midTree.ToList());
List<int> result = new List<int>();
Coding004.PreNode(tree, result);
Assert.Equal(JsonConvert.SerializeObject(preTree), JsonConvert.SerializeObject(result));
result.Clear();
Coding004.MidNode(tree, result);
Assert.Equal(JsonConvert.SerializeObject(midTree), JsonConvert.SerializeObject(result));
} 나무에 결점이 하나밖에 없어요.
///
///
///
[Fact]
public void One()
{
int[] preTree = { 1 };
int[] midTree = { 1 };
TreeNode tree = Coding004.Tree(preTree.ToList(), midTree.ToList());
List<int> result = new List<int>();
Coding004.PreNode(tree, result);
Assert.Equal(JsonConvert.SerializeObject(preTree), JsonConvert.SerializeObject(result));
result.Clear();
Coding004.MidNode(tree, result);
Assert.Equal(JsonConvert.SerializeObject(midTree), JsonConvert.SerializeObject(result));
} 완전 두 갈래 나무
///
///
/// 1
/// / \
/// 2 3
/// / \ / \
/// 4 5 6 7
///
[Fact]
public void All()
{
int[] preTree = { 1, 2, 4, 5, 3, 6, 7 };
int[] midTree = { 4, 2, 5, 1, 6, 3, 7 };
TreeNode tree = Coding004.Tree(preTree.ToList(), midTree.ToList());
List<int> result = new List<int>();
Coding004.PreNode(tree, result);
Assert.Equal(JsonConvert.SerializeObject(preTree), JsonConvert.SerializeObject(result));
result.Clear();
Coding004.MidNode(tree, result);
Assert.Equal(JsonConvert.SerializeObject(midTree), JsonConvert.SerializeObject(result));
} 엉뚱한 생각: 사고를 확장하고 상상을 발휘하다
1. 두 갈래 나무 익히기 2.두 갈래 나무의 몇 가지를 익히다.대열을 익히면 먼저 나온다.익숙하다
기타 시리즈
면접 문제[끝에서 끝까지 체인표 인쇄]
면접 문제【문자열 교체 공백】
면접 문제[2차원수 그룹에서의 찾기]
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
