두 갈래 나무 필기시험 면접 문제 집합

두 갈래 나무 깊이

    public int TreeDepth(TreeNode root) {
        if(root==null)
            return 0;
        int left=TreeDepth(root.left)+1;
        int right=TreeDepth(root.right)+1;
        return Math.max(left,right);
    }

판단 평형 두 갈래 나무

한 가지 방법은 두 갈래 나무의 깊이를 구하여 뿌리 노드부터 귀속시킬 수 있다.좌우 깊이를 다시 구하여 비교하다.마지막으로 잎 노드를 구하다.하지만 반복된다.또 다른 방법은 뒷순서를 이용하여 사고방식을 두루 훑어볼 수 있다.뿌리 결점을 두루 훑어보았을 때 좌우 나무는 이미 판단을 하였기 때문에 반복적으로 훑어보는 경우는 없을 것이다.

public class Solution {
    private boolean isBalanced=true;
    public boolean IsBalanced_Solution(TreeNode root){
        getDepth(root);
        return isBalanced;
    }
    public int getDepth(TreeNode root){
        if(root==null)
            return 0;
        int left=getDepth(root.left);
        int right=getDepth(root.right);
        if(Math.abs(left-right)>1)
            isBalanced=false;
        return right>left?right+1:left+1;
    }

}

두 갈래 검색 트리의 뒷순서 반복 시퀀스 여부를 판단합니다

예를 들어 수조 {5, 7, 6, 9, 11, 10, 8}은 두 갈래 검색 트리의 뒷순서를 훑어보는 서열입니다.발견 뿌리 노드 8576은 8보다 작고 8 왼쪽 나무, 91110은 8보다 크면 오른쪽 나무, 6은 왼쪽 나무 뿌리 노드, 10은 오른쪽 나무 뿌리 노드, 발견은 귀속 문제 방법: 이동 후 훑어보고 뿌리 노드보다 크면 오른쪽 나무이다.오른쪽 트리 노드를 훑어보고 오른쪽 트리에 노드 값이 루트 노드보다 작으면false로 돌아갑니다.왼쪽 나무, 오른쪽 나무에 대해 귀속 판단을 하다.

  public boolean judge(int[] a,int start,int end){
        if(start>=end)
            return true;
        int i=start;
        while(i

두 갈래 트리 중 하나가 되는 경로

제목 설명: 두 갈래 트리와 정수를 입력하고 두 갈래 트리의 결점 값과 정수를 입력하기 위한 모든 경로를 출력합니다.경로는 나무의 뿌리 결점에서 시작하여 잎 결점까지 내려가는 결점으로 경로를 형성합니다.DFS 질문, 스택도 사용할 수 있고 list도 사용할 수 있습니다.

    public ArrayList> FindPath(TreeNode root,int target) {
        ArrayList> all=new ArrayList>();
        if(root==null)
           return all;
        Stack stack=new Stack();
        FindPath(root, target,stack,all);
        return all;
     }
     

     
     void FindPath(TreeNode root,int target,Stack stack, ArrayList> all){
        if(root==null)
            return;
        if((root.left==null&&root.right==null)&&root.val==target){
                ArrayList list=new ArrayList<>();
                for(int i:stack){
                    list.add(new Integer(i));
                }
                list.add(new Integer(root.val));
                all.add(list);
        }else{
            stack.push(new Integer(root.val));
            FindPath(root.left,target-root.val,stack,all);
            FindPath(root.right, target-root.val, stack, all);
            stack.pop();
        }
     }
    

두 갈래 나무를 거울로 바꾸다

선순환하는 방법과 유사하다

    public void mirror(TreeNode node){
        if(node==null)
            return;
        TreeNode n=node.left;
        node.left=node.right;
        node.right=n;
        mirror(node.left);
        mirror(node.right);
    }

두 갈래 나무의 대칭 여부를 판단하다

왼쪽 노드의 오른쪽 트리와 오른쪽 노드의 왼쪽 트리는 같은 귀속을 사용합니다

    boolean isSymmetrical(TreeNode pRoot){
        if(pRoot==null)
            return true;
        return comRoot(pRoot.left,pRoot.right);
    }
    
    boolean comRoot(TreeNode left,TreeNode right){
        if(left==null)
            return right==null;
        if(right==null)
            return false;
        if(left.val!=right.val)
            return false;
        return comRoot(left.right, right.left)&&comRoot(left.left, right.right);
    }

나무의 하위 구조

두 그루의 두 갈래 나무 A, B를 입력하여 B가 A의 자 구조인지 아닌지를 판단한다.(ps: 우리는 빈 나무가 임의의 나무의 하위 구조가 아니라고 약속합니다) 첫 번째 단계: 뿌리 마디 값과 같은 노드를 찾습니다. 실제로는 나무의 역력입니다.차례로 실현될 수 있다.두 번째 단계: 트리 A에서 R을 루트 노드로 하는 하위 트리가 트리 B와 같은 구조를 가지고 있는지 판단한다.값이 다르면 틀림없이 다르다.만약 같다면 각자의 좌우 노드를 다시 귀속적으로 판단한다.조건을 종료하면 트리 A 또는 트리 B 루트 노드에 도달합니다.

public class Solution {
        
     public boolean HasSubtree(TreeNode root1,TreeNode root2) {
           boolean result=false;
           if(root1!=null&&root2!=null){
               if(root1.val==root2.val){
                   result=DoesTree1HaveTree2(root1,root2);
               }
               if(!result)
                   result=HasSubtree(root1.left, root2);
               if(!result)
                   result=HasSubtree(root1.right, root2);
           }
           return result;
        }
     
     public boolean DoesTree1HaveTree2(TreeNode root1,TreeNode root2){
         if(root1==null&&root2!=null)
             return false;
         if(root2==null)
             return true;
         if(root1.val!=root2.val)
             return false;
         return DoesTree1HaveTree2(root1.left, root2.left)&&DoesTree1HaveTree2(root1.right, root2.right);
     }
}

여러 줄 인쇄 두 갈래 나무

    public ArrayList > Print(TreeNode pRoot) {
        ArrayList> result=new ArrayList>();   
        if(pRoot==null)
            return result;
        Queue layer=new LinkedList<>();
        ArrayList list=new ArrayList();
       layer.add(pRoot);
       int start=0,end=1;
       while(!layer.isEmpty()){
           TreeNode cur=layer.remove();
           list.add(cur.val);
           start++;
           if(cur.left!=null)
               layer.add(cur.left);
           if(cur.right!=null)
               layer.add(cur.right);
           if(start==end){
               end=layer.size();
               start=0;
               result.add(list);
               list=new ArrayList<>();
           }
       }
       return result;
    }

지그재그 인쇄 두 갈래 나무

창고 후진 선출의 특성을 이용하여 두 창고 하나의 메모리 층 노드, 하나의 메모리 층 노드

    /*
     *  ， ，
     *  ， ， 。
     */
    //{8,6,10,5,7,9,11}
    public static ArrayList> Print(TreeNode pRoot) {
        ArrayList> all=new ArrayList>();  
        int layer=1;
        Stack s1=new Stack();
        Stack s2=new Stack();
        s1.push(pRoot);
        while(!s1.empty()||!s2.empty()){
            if(layer%2!=0){
                ArrayList temp=new ArrayList();
                while(!s1.empty()){
                    TreeNode node=s1.pop();
                    if(node!=null){
                        temp.add(node.val);
                        System.out.print(node.val + " ");
                        s2.push(node.left);
                        s2.push(node.right);
                    }
                }
                if(!temp.isEmpty()){
                    all.add(temp);
                    layer++;
                    System.out.println();
                }
            }else{
                ArrayList temp=new ArrayList();
                while(!s2.empty()){
                    TreeNode node=s2.pop();
                    if(node!=null){
                        temp.add(node.val);
                        System.out.print(node.val + " ");
                        s1.push(node.right);
                        s1.push(node.left);
                    }
                }
                if(!temp.isEmpty()){
                    all.add(temp);
                    layer++;
                    System.out.println();
                }
            }
            
        }
        return all;
    }

두 갈래 나무를 재구성하다

두 갈래 나무의 앞 순서와 중간 순서의 결과를 입력하십시오. 이 두 갈래 나무를 다시 만드십시오.입력한 앞 순서와 중간 순서의 결과에 중복된 숫자가 없다고 가정하십시오.예를 들어 앞 순서 반복 시퀀스 {1,2,4,7,3,5,6,8}와 중간 순서 반복 시퀀스 {4,7,2,1,5,3,8,6}를 입력하면 두 갈래 트리를 재건하고 되돌려줍니다.

    public TreeNode reConstructBinaryTree(int[] pre,int[] in){
        if(pre.length==0||in.length==0)
            return null;
        TreeNode node=new TreeNode(pre[0]);
        for(int i=0;i

두 번째 검색 트리의 k 노드

두 갈래 수색 트리를 정해 주십시오. 그 중 두 번째로 큰 결점을 찾아 주십시오.예를 들어, 5/\3 7/\/\2 4 6 8에서 세 번째 결점의 값은 결점 수치 크기 순서대로 4입니다.

public class Solution {
    int index=0;
    TreeNode KthNode(TreeNode root, int k)
    {
        if(root!=null){
            TreeNode node=KthNode(root.left,k);
            if(node!=null)
                return node;
            index++;
            if(index==k)
                return root;
            node=KthNode(root.right,k);
            if(node!=null)
                return node;
        }
        return null;
    }  
}