데이터 구조의 이 진 트 리 우 객 망 편

이 진 트 리 재건
제목 링크: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);
    }


}