输出单层结点

import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}*/
public class TreeLevel {
    public ListNode getTreeLevel(TreeNode root, int dep) {
        if(root==null||dep<=0){
            return null;
        }
        // write code here
        LinkedList<TreeNode> list = new LinkedList();
        //Stack<ListNode> depNodeCache = new Stack();
        list.add(root);
        int countDep = 1;
        int count = 0;
        //按层遍历
        while(!list.isEmpty()&&countDep<dep){
            count = list.size();
            //遍历下一层的所有子叶
            while(count>0){
                TreeNode node = list.removeFirst();
                if(node.left!=null){
                    list.add(node.left);
                }
                if(node.right!=null){
                    list.add(node.right);
                }
                count--;
            }
            countDep++;
        }
        
        return toListNode(list);
        
    }
    
    public static ListNode toListNode(LinkedList<TreeNode> list){
        ListNode curNode = null;
        ListNode pre = null;
        while(!list.isEmpty()){
            TreeNode node = list.removeLast();
            curNode = new ListNode(node.val);
            curNode.next = pre;
            pre = curNode;
        }
        return curNode;
    }
}

import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}*/
public class TreeLevel {
    
    ListNode result = new ListNode(-1);
    ListNode cur = result;
    
    public ListNode getTreeLevel(TreeNode root, int dep) {
        // write code here
        if (root == null || dep < 1) {
            return null;
        }
        if (dep == 1) {
            cur.next = new ListNode(root.val);
            cur = cur.next;
        }
        getTreeLevel(root.left, dep - 1);
        getTreeLevel(root.right, dep - 1);
        return result.next;
    }
}

//好像是剑指offer里面的一题，跟着差不多，双队列，有个小坑，见注释
//方法一
 public ListNode getTreeLevel(TreeNode root, int dep) {
       if(root==null||dep<=0) return null;
        Queue<TreeNode> queueFather=new LinkedList<TreeNode>();
        Queue<TreeNode> queueSon=new LinkedList<TreeNode>();
        queueFather.offer(root);
        int index=1;
        if(index==dep) return new ListNode(root.val);
        while(!queueFather.isEmpty()){
            TreeNode temp=queueFather.poll();
            if(temp.left!=null) queueSon.offer(temp.left);
            if(temp.right!=null)queueSon.offer(temp.right);
            if(queueFather.isEmpty()){
                index++;
                if(index==dep){
                    ListNode result=queueSon.isEmpty()?null:new ListNode(queueSon.poll().val);
                    ListNode cur=result;
                    while(!queueSon.isEmpty()) {
                        cur.next=new ListNode(queueSon.poll().val);
                        cur=cur.next;
                    }
                    return result;
                }
                queueFather=queueSon;
                queueSon=new LinkedList<TreeNode>();//此处有个坑，其实很简单，可能一开始没注意到，这里不能用clear方法，因为此时queueFather和queueSon指向同一个对象
                                                    //clear就全清了，如果想用clear就把上一句改成 queueFather=queueSon.clone(),那最开始的多台就不能用了，因为queue没有clonde方法
            }
        }
        return null;
    }
//方法二:递归
 ListNode result=new ListNode(0);
     ListNode cur=result;
     public ListNode getTreeLevel(TreeNode root, int dep) {
         if(root==null||dep<1) return null;
         if(--dep==0) {
             cur.next=new ListNode(root.val);
             cur=cur.next;
         }
         if(root.left!=null) getTreeLevel(root.left,dep);
         if(root.right!=null)getTreeLevel(root.right,dep);
         return result.next;
     }

1、定义队列a,b
2、首先头节点入a
3、依次取出a队列中的每个元素e，并打印。然后把e的左右节点入b队列，直到a取空
4、a，b互换，打印回车
5、重复3/4步，直到a为空，b也为空
6、打印结果即为按层遍历结果

// 因无需出队列，故此题以ArrayList代替队列
public ListNode getTreeLevel(TreeNode root, int dep) {
        if(root == null) return null;
        ArrayList<TreeNode> arr = new ArrayList<>();
        arr.add(root);
        return foo(arr,dep-1);
    }
    
    public ListNode foo(ArrayList<TreeNode> arr,int dep){
        if(dep == 0){
            ListNode head = new ListNode(arr.get(0).val);
            ListNode cur = head;
            for(int i = 1;i < arr.size();i++){
                cur.next = new ListNode(arr.get(i).val);
                cur = cur.next;
            }
            return head;
        }
        
        ArrayList<TreeNode> narr = new ArrayList<TreeNode>();
        for(int i = 0;i < arr.size();i++){
            if(arr.get(i).left != null)
            	narr.add(arr.get(i).left);
            if(arr.get(i).right != null)
            	narr.add(arr.get(i).right);
        }
        return foo(narr,dep-1);
    }

public ListNode getTreeLevel(TreeNode root, int dep) {
		// write code here
		//如果需要第一层，那么把第一层返回
		if(dep==1){
			return new ListNode(root.val);
		}
		//采用两个队列来控制层次遍历
		Queue<TreeNode> qu1=new LinkedList<TreeNode>();
		Queue<TreeNode> qu2=new LinkedList<TreeNode>();
		//记录目前的层数
		int nowDep=1;
		//首先设置一个表头和一个操作指针
		ListNode head=new ListNode(0);
		ListNode p=head;
		//首先往qu1中加入根节点
		qu1.add(root);
		while(root!=null){
			System.out.println("刚刚进入while");
			//首先判断当前层是否为需要的层
			if(nowDep==dep){
				while(!qu1.isEmpty()){
				//	System.out.println("返回层的值："+qu1.peek().val);
					ListNode newNode=new ListNode(qu1.poll().val);
					p.next=newNode;
					p=newNode;
				}
				return head.next;
			}
			/*若qu1内元素所在的层并不是指定输出的层，则进行下一层的装入,首先是把
				下一层的元素全部装入qu2,然后再把qu2内的元素全部装入qu1
			*/
			System.out.println("进入内部第一个while前");
			while(!qu1.isEmpty()){
				TreeNode nowNode=qu1.poll();
				System.out.println("qu1出队"+nowNode);
				qu2.add(nowNode.left);
				qu2.add(nowNode.right);
			}
			while(!qu2.isEmpty()){
				qu1.add(qu2.poll());
			}
			//此层后，进行层数加1
			nowDep++;
		}
		return new ListNode(root.val);
	}

//用null 分辨层
public class TreeLevel {
    public ListNode getTreeLevel(TreeNode root, int dep) {
        Queue<TreeNode> q=new LinkedList<TreeNode>();
        TreeNode t=null;
        ListNode head=new ListNode(0);
        ListNode cur=head;
        ListNode tmp=null;
        int k=0;
        q.add(null);
        q.add(root);
        while(!q.isEmpty()){
            t=q.poll();
            if(t==null){
                k++;
                if(k==dep)
                	break;
                q.add(null);
            }
            else{
                if(t.left!=null)
                    q.add(t.left);
                if(t.right!=null)
                    q.add(t.right);
            }
        }
        
        while(!q.isEmpty()){
            tmp=new ListNode(q.poll().val);
            cur.next=tmp;
            cur=cur.next;
        }
        return head.next;
    }
}

思路

1. 要获取指定深度的节点，只需在二叉树的先序遍历过程中加上深度值即可。
2. 由于先序遍历是先访问左孩子、再访问右孩子，所以某一层的左孩子一定先访问到，右孩子一定后访问到。

代码

只要在先序遍历函数上加上两个参数即可：

1. 当前深度；

2. 目标深度 若当前深度和目标深度一致时，将当前节点输出，并直接return回溯，无需再往下递归了！节约一定的开销！

    private ListNode node = new ListNode(-1);
    private ListNode first = node;
    public ListNode getTreeLevel(TreeNode root, int dep) {
        if ( root==null || dep<=0 ) return null;
   
        preOrder( root, 1, dep );
   
        return first.next;
    }
   
    private void preOrder( TreeNode root, int level, int dep ){
        if ( root==null ) return;
   
        if ( level==dep ) {
            node.next = new ListNode(root.val);
            node = node.next;
            return;
        }
   
        preOrder(root.left, level+1, dep);
        preOrder(root.right, level+1, dep);
    }
   

public class TreeLevel {
	    MyListNode list = new MyListNode();
	    public ListNode getTreeLevel(TreeNode root, int dep) {
	       // write code here
	       vistTree(root,1,dep);
	       return list.getHead();
	        
	    }
	    // 因为要求的函数没有带有深度记录参数 为了方便 自己重写了一个可以记录深度的函数

	    private void vistTree(TreeNode root,int depth,int goal){
				if(depth == goal){
	                list.addToList(root.val);
	                return ;
	            }else{
					if(root.left != null){
	                    vistTree(root.left,depth+1,goal);
	                }
	                if(root.right != null){
	                    vistTree(root.right,depth+1,goal);
	                }
	            }
	      
	    }
	    /**
             * 自己定义的一个内部类 主要用来保存访问时候的数据
              */
	      class MyListNode{
				private ListNode head;
	            private ListNode last;
	            public ListNode getHead(){
	                return head;
	            }
	            public void addToList(int val){
	               if(head == null){
	                  head = new ListNode(val);
	                   last = head;
	               }else{
	                  last.next = new ListNode(val);
	                  last = last.next;
	               }
	            }
	        }
	}