本文共 2325 字，大约阅读时间需要 7 分钟。

1. 问题描述：

Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth(if you have a tree whith depth D, you're have D linked lists)

题目的意思是：给出一棵二叉树，以链表的形式返回二叉树的某一层的所有节点

2. 对树的操作无非是深度优先搜索和宽度优先搜索，由于涉及到的是树的层次，所以我们应该采用的是宽度优先搜索，使用宽搜的时候需要借助于队列来进行元素之间层次的处理，我们先要把树的根节点存到队列中，使用循环，当队列不为空的时候我们弹出一个节点，采用的策略是弹出一个节点如果左右节点不为空的情况下加入当前的左右节点，并且对弹出的节点进行层次上的判断，这里由于涉及到层高的问题所以可以对树节点进行封装，里面包括树的节点与当前节点的层高这两个属性，这样我们在压栈并且弹出栈的时候判断当前元素的层高是多少，假如层高满足题目中所给出的高度，那么创建链表的节点，把所有创建的节点连接起来即可

代码如下：

import java.util.LinkedList;import java.util.Queue;public class TreeLevel {	public static void main(String[] args) {		//以链表的形式返回BST中某一层的所有节点		TreeNode
   
     root = new TreeNode
    
     (1);		TreeNode
     
       l = new TreeNode
      
       (2);		TreeNode
       
         r = new TreeNode
        
         (3); TreeNode
         
           ll = new TreeNode
          
           (4); TreeNode
           
             lr = new TreeNode
            
             (5); TreeNode
             
               rl = new TreeNode
              
               (6); TreeNode
               
                 rr = new TreeNode
                
                 (7); root.left = l; root.right = r; l.left = ll; l.right = lr; r.left = rl; r.right = rr; int depth = 3; ListNode
                 
                   head = getTreeLevel(root, depth); ListNode
                  
                    p = head; while(p != null){ System.out.print(p.value + " "); p = p.next; } } //借助队列使用宽度优先搜索来解决 private static ListNode
                   
                     getTreeLevel(TreeNode
                    
                      root, int depth) { Queue
                     
                       queue = new LinkedList<>(); queue.offer(new NodeAndHeight(root, 1)); ListNode
                      
                        head = null; ListNode
                       
                         p = null; while(!queue.isEmpty()){ NodeAndHeight poll = queue.poll(); if(poll.level == depth){ if(head == null){ head = new ListNode
                        
                         (poll.node.val); p = head; } else{ ListNode
                         
                           newNode = new ListNode
                          
                           (poll.node.val); p.next = newNode; p = p.next; } }else if(poll.level > depth){ break; } if(poll.node.left != null){ queue.offer(new NodeAndHeight(poll.node.left, poll.level + 1)); } if(poll.node.right != null){ queue.offer(new NodeAndHeight(poll.node.right, poll.level + 1)); } } //返回链表的头结点 return head; } //将链表节点封装成为高度与节点的类 //也可以使用边遍历边检查的方法来解决 //class必须声明为static private static class NodeAndHeight{ private TreeNode
                           
                             node; private int level; NodeAndHeight(TreeNode
                            
                              node, int level){ this.node = node; this.level = level; } }}
                            
                           
                          
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

链表节点定义为：

public class ListNode
   
     {	public ListNode
    
      next;	public T value;	ListNode(T value){		this.value = value;	}		@Override	public String toString() {		return "ListNode [value=" + value + "]";	}	}
    
   

转载地址：http://hawg.baihongyu.com/