데이터 구조의 이 진 트 리 우 객 망 편
20975 단어 데이터 구조
제목 링크:https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=13&tqId=11157&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
이 진 트 리 의 앞 순 서 를 입력 하고 중간 순 서 를 옮 겨 다 니 는 결 과 를 입력 하 십시오. 이 이 진 트 리 를 다시 만 드 십시오.입력 한 앞 순서 와 중간 순 서 를 옮 겨 다 니 는 결과 에 중복 되 는 숫자 가 없다 고 가정 합 니 다.예 를 들 어 앞 순서 옮 겨 다 니 기 시퀀스 {1, 2, 4, 7, 3, 5, 6, 8} 과 중간 순서 옮 겨 다 니 기 시퀀스 {4, 7, 2, 1, 5, 3, 8, 6} 을 입력 하면 이 진 트 리 를 다시 만 들 고 돌아 갑 니 다.
import java.util.Arrays;
public class Solution{
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if(pre.length==0||in.length==0)
return null;
int root=pre[0];
TreeNode node=new TreeNode(root);
int index=-1;
for(int i=0;i<in.length;i++){
if(in[i]==root){
index=i;
break;
}
}
if(index==-1)
return null;
node.left=reConstructBinaryTree(Arrays.copyOfRange(pre, 1, index+1),Arrays.copyOfRange(in, 0, index));
node.right=reConstructBinaryTree(Arrays.copyOfRange(pre, index+1, pre.length),Arrays.copyOfRange(in, index+1, in.length));
return node;
}
}
나무의 서브 구조
제목 링크https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88?tpId=13&tqId=11170&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
두 개의 이 진 트 리 A, B 를 입력 하여 B 가 A 의 서브 구조 인지 아 닌 지 를 판단 합 니 다.
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
if(root1==null)
return false;
if(root2==null)
return false;// root2 ,
return isSubTree(root1,root2)||HasSubtree(root1.left,root2)||HasSubtree(root1.right,root2);
}
public boolean isSubTree(TreeNode root1,TreeNode root2){
if(root2==null)
return true;
if(root1==null)
return false;
if(root1.val==root2.val)
return isSubTree(root1.left,root2.left)&&isSubTree(root1.right,root2.right);
return false;
}
}
이 진 트 리 미 러
문제: 주어진 이 진 트 리 를 조작 하여 원본 이 진 트 리 의 미 러 로 변환 합 니 다.입력 설명: 이 진 트 리 의 미 러 정의: 원본 이 진 트 리 8 / \ 6 10 / \ / \ 5 7 9 11 미 러 이 진 트 리 8 / \ 10 6 / \ / \ 11 9 7 5
제목 링크:https://www.nowcoder.com/practice/564f4c26aa584921bc75623e48ca3011?tpId=13&tqId=11171&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
public void Mirror(TreeNode root) {
if(root==null)
return;
TreeNode right=root.right;
TreeNode left=root.left;
root.left=right;
root.right=left;
Mirror(root.left);
Mirror(root.right);
}
두 갈래 검색 트 리 의 뒷 순서 옮 겨 다 니 기 시퀀스
문제: 정수 배열 을 입력 하여 이 배열 이 어떤 이 진 트 리 의 뒤 순 서 를 옮 겨 다 니 는 결과 인지 판단 합 니 다.그렇다면 Yes 를 출력 합 니 다. 그렇지 않 으 면 No 를 출력 합 니 다.입력 한 배열 의 임의의 두 숫자 가 서로 다르다 고 가정 합 니 다.http://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd?tpId=13&tqId=11176&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
import java.util.Arrays;
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence==null||sequence.length==0)
return false;
return this.isBST(sequence,0,sequence.length-1);
}
public boolean isBST(int[] arr,int start,int end){
if(start>=end)
return true;
int current=arr[end];//
int i=start;
while(i//
}
for(int j=i;jif(arr[j]return false;// false
}
return isBST(arr,start,i-1)&&isBST(arr,i,end-1);
}
}
층 차 를 편력 하 다
문제: 이 진 트 리 의 모든 노드 를 위 에서 아래로 인쇄 하고 같은 층 의 노드 는 왼쪽 에서 오른쪽으로 인쇄 합 니 다.
import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
//! , null, list !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
//if(root==null)
// return null;
Queue<TreeNode> queue=new LinkedList<TreeNode>();
ArrayList<Integer> list=new ArrayList<Integer>();
if(root==null)
return list;
queue.offer(root);
while(!queue.isEmpty()){
TreeNode node=queue.poll();
list.add(node.val);
if(node.left!=null)
queue.offer(node.left);
if(node.right!=null)
queue.offer(node.right);
}
return list;
}
}
이 진 트 리 와 특정한 값 의 경로
제목 설명
이 진 트 리 와 정 수 를 입력 하고 이 진 트 리 의 노드 값 과 정 수 를 입력 하기 위 한 모든 경 로 를 출력 합 니 다.경 로 는 나무의 뿌리 결점 에서 부터 잎 결점 이 지나 가 는 결점 까지 하나의 경 로 를 형성 하 는 것 으로 정의 된다.https://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca?tpId=13&tqId=11177&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
import java.util.ArrayList;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
private ArrayList> arraylist=new ArrayList>();
private ArrayList list=new ArrayList();
public ArrayList> FindPath(TreeNode root,int target) {
if(root==null)
return arraylist;
list.add(root.val);
target-=root.val;
if(target==0&&root.left==null&&root.right==null)
arraylist.add(new ArrayList(list));//
FindPath(root.left,target);
FindPath(root.right,target);
list.remove(list.size()-1);
return arraylist;
}
}
밸 런 스 트 리 인지 아 닌 지 판단 하기
이 진 트 리 를 입력 하여 이 진 트 리 가 균형 이 잡 힌 이 진 트 리 인지 판단 하 십시오.https://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222?tpId=13&tqId=11192&rp=2&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
if(root==null)
return true;
int flag=Math.abs(TreeDepth(root.left)-TreeDepth(root.right));
if(flag>1)
return false;
return IsBalanced_Solution(root.left)&&IsBalanced_Solution(root.right);
}
public int TreeDepth(TreeNode root){
if(root==null)
return 0;
int depth;
depth=1+Math.max(TreeDepth(root.left),TreeDepth(root.right));
return depth;
}
}
두 갈래 검색 트 리 가 양 방향 링크 로 바 뀌 었 습 니 다.
문제 설명 은 이 진 트 리 를 입력 하고 이 이 진 트 리 를 정렬 된 양 방향 링크 로 변환 합 니 다.새로운 노드 를 만 들 수 없고 트 리 의 노드 포인터 의 방향 만 조정 할 수 있 습 니 다.
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
TreeNode phead; //
TreeNode realhead; //
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree==null)
return pRootOfTree;
ConvertSub(pRootOfTree);
return realhead;
}
//
public void ConvertSub(TreeNode root){
if(root==null)
return ;
ConvertSub(root.left);
if(phead==null){
phead=root;
realhead=root;
}
else{
phead.right=root;
root.left=phead;
phead=root;
}
ConvertSub(root.right);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.