알고리즘 총결의 두 갈래 나무
81792 단어 데이터 구조와 알고리즘
기사 목록
두 갈래 나무를 두루 다니다.
두 갈래 나무의 뿌리 결점 루트를 정하려면 두 갈래 나무의 선순, 중순과 후속 역행 (2차원 그룹의 형식) 을 차례로 되돌려 주십시오.
귀속 방식
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}*/
public class TreeToSequence {
public int[][] convert(TreeNode root) {
List<Integer> list1 = new ArrayList<Integer>();
List<Integer> list2 = new ArrayList<Integer>();
List<Integer> list3 = new ArrayList<Integer>();
qianxu(list1,root);
zhongxu(list2,root);
houxu(list3,root);
int[][] res = new int[3][list1.size()];
for(int i=0;i<list1.size();i++){
res[0][i] = list1.get(i);
res[1][i] = list2.get(i);
res[2][i] = list3.get(i);
}
return res;
}
private void qianxu(List<Integer> list,TreeNode tree){
if(tree==null)
return;
list.add(tree.val);
qianxu(list,tree.left);
qianxu(list,tree.right);
}
private void zhongxu(List<Integer> list,TreeNode tree){
if(tree==null)
return;
zhongxu(list,tree.left);
list.add(tree.val);
zhongxu(list,tree.right);
}
private void houxu(List<Integer> list,TreeNode tree){
if(tree==null)
return;
houxu(list,tree.left);
houxu(list,tree.right);
list.add(tree.val);
}
}
비귀속 방식
1. 먼저 생각을 반복한다. (1)cur=root,cur입고,cur출고list(2)cur오른쪽 아이가 비어 있는지, 비어 있지 않으면 입고하는지 판단한다.cur 왼쪽 아이가 비어 있는지 판단하고, 비어 있지 않으면 창고에 들어갑니다.중서 반복 사고방식: (1)cur=root,cur가 비어 있지 않으면 창고에,cur=cur.left, 그리고 반복 (1)(2)cur가 비어 있으면 창고 꼭대기에list를 저장하고 다른cur=cur.right;반복 (1) (2) 3.뒷순서 반복 사고방식: (1) 두 노드 정의 h=root, c=창고 꼭대기 노드 (초기는null) (2)tree 입고, c=tree;만약 c.left가 비어 있지 않으면 h!=c.left와 c.right, c입고(3) 그렇지 않으면 c.right가 비어 있지 않고 h!=c.right, c입고(4)(2)(3)이 모두 만족스럽지 않으면 h=c(창고 꼭대기 노드), 창고 꼭대기 출고list 저장, 중복(2)(3)(4)
public class TreeToSequence {
public int[][] convert(TreeNode root) {
List<Integer> list1 = new ArrayList<Integer>();
List<Integer> list2 = new ArrayList<Integer>();
List<Integer> list3 = new ArrayList<Integer>();
qianxu(list1,root);
zhongxu(list2,root);
houxu(list3,root);
int[][] res = new int[3][list1.size()];
for(int i=0;i<list1.size();i++){
res[0][i] = list1.get(i);
res[1][i] = list2.get(i);
res[2][i] = list3.get(i);
}
return res;
}
//
private void qianxu(List<Integer> list,TreeNode tree){
if(tree==null)
return;
Stack<TreeNode> temp = new Stack<TreeNode>();
temp.push(tree);
while(!temp.empty()){
TreeNode cur = temp.pop();
list.add(cur.val);
if(cur.right!=null)
temp.push(cur.right);
if(cur.left!=null)
temp.push(cur.left);
}
}
//
private void zhongxu(List<Integer> list,TreeNode tree){
if(tree==null)
return;
Stack<TreeNode> temp = new Stack<TreeNode>();
TreeNode cur = tree;
while(!temp.empty()||cur!=null){
if(cur!=null){
temp.push(cur);
cur = cur.left;
}else{
cur = temp.pop();
list.add(cur.val);
cur = cur.right;
}
}
}
//
private void houxu(List<Integer> list,TreeNode tree){
if(tree==null)
return;
TreeNode h = tree;
TreeNode c = null;
Stack<TreeNode> temp = new Stack<TreeNode>();
temp.push(tree);
while(!temp.empty()){
c = temp.peek();
if(c.left!=null && (h!=c.left && h!=c.right)){
temp.push(c.left);
c = temp.peek();
}else if(c.right!=null && h!=c.right){
temp.push(c.right);
c = temp.peek();
}else{
h = c;
TreeNode tmp = temp.pop();
list.add(tmp.val);
}
}
}
}
계층별로 인쇄
두 갈래 나무가 있는데 알고리즘을 설계하여 이 두 갈래 나무의 사고방식을 차원에 따라 인쇄하십시오. (1) A를 팀에서 내보내고 A의 자식을 팀에 넣고 nlast=A의 마지막에 들어간 자식(맨 오른쪽 아이)을 업데이트합니다.(2) 마지막 출력 팀의 A를 인쇄하고 last와 비교합니다. 같으면 인쇄하고 줄을 바꾸고last=nlast를 업데이트합니다. 다르면 계속
import java.util.*;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}*/
public class TreePrinter {
public int[][] printTree(TreeNode root) {
if(root==null)
return null;
TreeNode print = null;
TreeNode last = null;
TreeNode nlast = null;
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> rows = new ArrayList<Integer>();
LinkedList<TreeNode> q = new LinkedList();
last = root;
q.offer(root);
while(!q.isEmpty()){
print = q.poll();
rows.add(print.val);
if(print.left!=null){
q.offer(print.left);
nlast = print.left;
}
if(print.right!=null){
q.offer(print.right);
nlast = print.right;
}
if(print == last){
res.add(rows);
rows = new ArrayList<Integer>();
last = nlast;
}
}
int[][] result = new int[res.size()][];
for(int i=0;i<res.size();i++){
result[i] = new int[res.get(i).size()];
for(int j=0;j<res.get(i).size();j++){
result[i][j] = res.get(i).get(j);
}
}
return result;
}
}
두 갈래 나무 서열화
우선 두 갈래 트리의 순서화 방식을 소개합니다. 순서화된 결과 문자열을str로 가정하면 처음에str는 빈 문자열과 같습니다.먼저 두 갈래 나무를 훑어보고 빈 노드를 만나면str의 끝에'#!'를 붙여서"#"은 이 노드가 비어 있고 노드 값이 존재하지 않는다는 것을 나타냅니다. 물론 다른 특수 문자를 사용할 수도 있습니다. "!"값의 끝을 나타냅니다.만약 비어 있지 않은 노드를 만났다면, 노드 값이 3이라고 가정하면str의 끝에'3!'을 추가합니다.이제 트리의 순서를 정렬해 주십시오.주어진 트리의 루트 결점 루트, 두 갈래 트리 서열화된 문자열을 되돌려주십시오.
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}*/
public class TreeToString {
public String toString(TreeNode root) {
String res = "";
if(root==null)
return res;
TreeNode temp = root;
LinkedList<TreeNode> stack = new LinkedList<TreeNode>();//HashSet、HashMap、ArrayList、LinkedList null
stack.push(temp);
while(!stack.isEmpty()){
TreeNode cur = stack.pop();
if(cur==null)
res = res + "#!";
else{
res = res + String.valueOf(cur.val) + "!";
stack.push(cur.right);
stack.push(cur.left);
}
}
return res;
}
}
평형 두 갈래 나무 판단
두 갈래 나무가 있는데 이 두 갈래 나무가 균형 잡힌 두 갈래 나무인지 아닌지를 판단하는 알고리즘을 설계해 주십시오.두 갈래 나무의 뿌리 결점 루트를 지정하려면bool값을 되돌려주십시오. 이 나무가 균형 두 갈래 나무인지 여부를 나타냅니다.사고방식: (1) 균형 두 갈래 나무: 각 노드의 좌우 나무의 높이 차이가 1을 초과하지 않고 빈 나무도 균형 두 갈래 나무(2)로 돌아가서 좌우 나무의 깊이를 얻는다. 깊이가 0보다 작거나 좌우 나무의 깊이 차이가 1보다 크면false로 돌아간다.그렇지 않으면 계속 귀속되어 나무의 깊이(>=0)를 되돌릴 수 있다는 것은 균형 두 갈래 나무라는 것을 의미한다
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}*/
public class CheckBalance {
public boolean check(TreeNode root) {
return getDepth(root)>=0;
}
private int getDepth(TreeNode root){
if(root==null)
return 0;
int left = getDepth(root.left);
int right = getDepth(root.right);
if(left<0||right<0)
return -1;
if(Math.abs(left-right)>1)
return -1;
return Math.max(left,right)+1;
}
}
완전 두 갈래 나무 판단
두 갈래 나무가 있는데, 그것이 완전한 두 갈래 나무인지 아닌지를 판단하는 알고리즘을 설계해 주십시오.두 갈래 나무의 뿌리 결점 루트를 지정하려면bool 값을 되돌려 주십시오. 이것은 완전한 두 갈래 나무인지 여부를 나타냅니다.나무의 결점 개수는 500보다 작다.사고방식: (1) 새 대열을 만들고 층별로 두 갈래 나무를 훑어본다(2) 만약에 노드가 있는 왼쪽 아이가 비어 있고 오른쪽 아이가 비어 있지 않으면false로 되돌아간다. 만약에 왼쪽 아이가 비어 있지 않고 오른쪽 아이가 비어 있다면 이 노드는 반드시 잎 노드이고 잎 노드가 아니라면false로 되돌아가야 한다.순환 도중에false를 되돌리지 않았습니다. 마지막으로true를 되돌려줍니다.
public class CheckCompletion {
public boolean chk(TreeNode root) {
if(root==null)
return true;
Queue<TreeNode> q = new LinkedList<>();
boolean leaf = false;
q.offer(root);
while(!q.isEmpty()){
TreeNode temp = q.poll();
if((leaf&&(temp.left!=null||temp.right!=null))||(temp.left==null&&temp.right!=null))
return false;
if(temp.left!=null&&temp.right==null)
leaf = true;
if(temp.left!=null)
q.offer(temp.left);
if(temp.right!=null)
q.offer(temp.right);
}
return true;
}
}
종이접기의 접힌 흔적 판단
쪽지를 책상 위에 세로로 놓고 쪽지 밑에서 위로 반으로 접어 접힌 흔적을 눌러 펴주세요.이때 접힌 흔적이 하나 있는데 돌출된 ⽅는 쪽지의 등을 가리키는데 이 접힌 흔적을'하'접힌 흔적이라고 한다.돌출된 ⽅向 지향 쪽지 정⾯의 접힌 흔적을'상'접힌 흔적이라고 한다.만약 매번 아래에서 위로 반으로 접는다면, 반으로 N번 접는다.모든 꺾인 흔적의 방향을 위에서 아래로 계산해 주십시오.접는 횟수 n을 지정하면 위에서 아래로 접힌 흔적의 수조를 되돌려 주십시오. 아래 접힌 흔적이면 해당 요소는'down'이고 위 접힌 흔적은'up'입니다.테스트 예시: 1 반환: ["down"] 사고방식: 첫 번째 종이접기, 접힌 흔적은 아래접기, 두 번째 종이접기, 양쪽에 아래접힌 흔적과 윗접힌 흔적이 각각 많으면 두 갈래 나무의 좌우 아이와 맞먹는다. 종이접기 한 번 노드마다 좌우 두 아이가 증가한다.이것은 두 갈래 나무로 가득 차 있는데, 위에서 아래로 꺾인 흔적이 바로 이 두 갈래 나무를 중순으로 두루 훑어보는 것이다.
public class FoldPaper {
public String[] foldPaper(int n) {
List<String> temp = new LinkedList<String>();
fold(1,n,true,temp);
String[] res = new String[temp.size()];
for(int i=0;i<temp.size();i++){
res[i] = temp.get(i);
}
return res;
}
private void fold(int i,int n,boolean flag,List<String> list){//flag
if(i>n)
return;
fold(i+1,n,true,list);
if(flag)
list.add("down");
else
list.add("up");
fold(i+1,n,false,list);
}
}
두 갈래 트리 오류 노드 검색
두 갈래 나무 한 그루는 원래 두 갈래 나무를 검색했지만, 그 중 두 개의 노드가 위치를 바꾸어 이 두 갈래 나무가 더 이상 두 갈래 나무를 검색하지 않도록 했습니다. 이 두 개의 오류 노드를 찾아 값을 되돌려 주십시오.두 갈래 나무의 결점의 값이 각각 다르다는 것을 보증한다.한 그루의 나무의 뿌리 결점을 지정하려면 두 개의 바뀐 위치의 값을 되돌려주십시오. 그 중에서 작은 값은 앞에 있습니다.사고방식: (1) 중간 순서로 두 갈래 나무를 검색하면 그 결과는 상승 순서에 따라 배열되고 (2) 역순서가 한 번만 나타나면 크기의 노드는 잘못된 노드이다.만약 두 번의 역순이 발생한다면 첫 번째 역순의 큰 노드와 두 번째 역순의 작은 노드가 두 개의 잘못된 노드이다.
public class FindErrorNode {
public int[] findError(TreeNode root) {
List<Integer> temp = new ArrayList<Integer>();
int[] res = new int[2];
int index = 0;//
zhongxu(root,temp);
for(int i=0;i<temp.size()-1;i++){
if(temp.get(i)>temp.get(i+1)){
index++;
if(index==1){
res[1] = temp.get(i);
res[0] = temp.get(i+1);
}else
res[0] = temp.get(i+1);
}
}
return res;
}
public void zhongxu(TreeNode root,List<Integer> temp){
if(root==null)
return;
zhongxu(root.left,temp);
temp.add(root.val);
zhongxu(root.right,temp);
}
}
트리에서 가장 먼 거리
두 갈래 나무의 노드 A에서 출발하여 위나 아래로 갈 수 있지만 길가의 노드는 한 번만 지나갈 수 있다. 노드 B에 도착할 때 경로의 노드 수를 A에서 B까지의 거리라고 부른다.주어진 두 갈래 나무에 대해 전체 나무의 노드 간의 최대 거리를 구한다.두 갈래 나무의 머리 결점 루트를 정하려면 최대 거리로 돌아가십시오.보증점수는 2보다 크고 500보다 작다.사고방식: 최대 거리는 세 가지 상황만 있을 수 있다. (1) 루트 왼쪽 나무의 최대 거리.(2) 루트 오른쪽 트리의 최대 거리;(3) 루트 왼쪽 나무에서 루트 왼쪽 아이와 가장 먼 결점 거리에 루트 자신을 추가한다.게다가 루트 오른쪽 나무에서 루트 오른쪽 아이와 가장 먼 결점의 거리 세 개 중 가장 큰 것은 바로 원하는 것이다
public class LongestDistance {
public int findLongest(TreeNode root) {
int[] res = new int[1];
houxu(root,res);
return res[0];
}
private int houxu(TreeNode root,int[] res){
if(root==null)
return 0;
int left = houxu(root.left,res);
int right = houxu(root.right,res);
res[0] = Math.max(res[0],left+right+1);
return Math.max(left,right)+1;
}
}
최대 두 갈래 검색 서브트리
두 갈래 나무가 있는데 그 중 모든 노드의 값이 다르다. 노드가 가장 많은 검색 두 갈래 나무를 찾아서 이 나무의 머리 노드로 돌아간다.두 갈래 나무의 머리 결점 루트를 지정하면 원하는 머리 결점을 되돌려주십시오. 여러 노드가 가장 많은 하위 나무가 나타나면 머리 결점 권한 값이 가장 큰 것을 되돌려줍니다.사고방식: 두 갈래 검색 트리: 왼쪽 트리가 비어 있지 않으면 왼쪽 트리의 모든 결점의 값이 뿌리 결점의 값보다 작다.만약 그것의 오른쪽 트리가 비어 있지 않으면 오른쪽 트리의 모든 결점의 값은 그것의 뿌리 결점의 값보다 크다.그것의 왼쪽, 오른쪽 나무도 각각 두 갈래 정렬 나무이다.(1) 전체적인 과정은 두 갈래 나무의 뒷부분을 두루 훑어본다.(2) 현재 결점을cur로 기록할 때 먼저cur의 왼쪽 트리를 훑어보고 4개의 정보를 수집한다. 각각 왼쪽 트리에서 최대 두 갈래 트리의 머리 결점, 결점 수, 트리의 최대 값과 트리의 최소 값을 검색한다.cur의 오른쪽 트리를 두루 돌아다니며 상기 네 가지 정보를 수집합니다.(3) 2단계에서 수집한 정보에 따라 만족 여부를 판단한다.cur를 머리로 하는 서브트리는 전체적으로 두 갈래 트리를 검색하고 만족스러우면cur로 돌아간다.만족하지 않으면 왼쪽 트리와 오른쪽 트리로 돌아가 각각 최대 두 갈래 트리에서 노드 수가 많은 두결점을 검색합니다.
public class MaxSubtree {
public TreeNode getMax(TreeNode root) {
int[] temp = new int[3];
return houxu(root,temp);
}
private TreeNode houxu(TreeNode root,int[] temp){
if(root==null){
temp[0]=Integer.MIN_VALUE;
temp[1]=Integer.MAX_VALUE;
temp[2]=0;
return null;
}
TreeNode left = houxu(root.left,temp);
int l_max = temp[0];//
int l_min = temp[1];//
int l_num = temp[2];//
TreeNode right = houxu(root.right,temp);
int r_max = temp[0];
int r_min = temp[1];
int r_num = temp[2];
// temp[0],temp[1] ， r_max==Integer.MIN_VALUE,l_min(Integer.MAX_VALUE)
temp[0] = Math.max(r_max,root.val);
temp[1] = Math.min(l_min,root.val);
if(left==root.left && right==root.right && l_max<root.val && r_min>root.val){
temp[2] = l_num+r_num+1;
return root;
}
temp[2] = Math.max(l_num,r_num);//
return l_num>r_num?left:right;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
두 갈래 나무의 깊이가 두루 다니다텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
