题目描述
对于一棵二叉树，请设计一个算法，创建含有某一深度上所有结点的链表。
给定二叉树的根结点指针TreeNode* root，以及链表上结点的深度，请返回一个链表ListNode，代表该深度上所有结点的值，请按树上从左往右的顺序链接，保证深度不超过树的高度，树上结点的值为非负整数且不超过100000。
思路：书本150页。深度以及高度从1开始算，国外多从0开始计算。这里采用1.
方法1：深度优先搜索
代码如下：
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) {
ArrayList<LinkedList<TreeNode>> lists= createLevelLinkedList(root);
LinkedList<TreeNode> list=lists.get(dep-1);
ListNode p=new ListNode(list.get(0).val);
ListNode q=p;
for(int i=1;i<list.size();i++){
p.next=new ListNode(list.get(i).val);
p=p.next;
}
return q;
}
void createLevelLinkedList(TreeNode root,ArrayList<LinkedList<TreeNode>>lists,int level){
if(root==null) return;
LinkedList<TreeNode> list=null;
if(lists.size()==level){
list=new LinkedList<TreeNode>();
lists.add(list);
}else{
list=lists.get(level);
}
list.add(root);
createLevelLinkedList(root.left,lists,level+1);
createLevelLinkedList(root.right,lists,level+1);
}
ArrayList<LinkedList<TreeNode>>createLevelLinkedList(TreeNode root){
ArrayList<LinkedList<TreeNode>> lists=new ArrayList<LinkedList<TreeNode>>();
createLevelLinkedList(root,lists,0);
return lists;
}
}
方法2：广度优先搜索
代码如下：
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) {
ListNode ret=null;
if(root==null) return null;
ArrayList<LinkedList<TreeNode>> lists= createLevelLinkedList(root);
LinkedList<TreeNode>list=lists.get(dep-1);
ListNode head=new ListNode(list.get(0).val);
ListNode tmp=head;
for(int i=1;i<list.size();i++){
tmp.next=new ListNode(list.get(i).val);
tmp=tmp.next;
}
return head;
}
ArrayList<LinkedList<TreeNode>> createLevelLinkedList(TreeNode root){
ArrayList<LinkedList<TreeNode>> ret=new ArrayList<>();
LinkedList<TreeNode> cur=new LinkedList<>();
LinkedList<TreeNode> parent=new LinkedList<>();
cur.add(root);
ret.add(cur);
parent=cur;
while(parent.size()!=0){
cur=new LinkedList<>();
for(TreeNode node:parent){
if(node.left!=null)
cur.add(node.left);
if(node.right!=null)
cur.add(node.right);
}
ret.add(cur);
parent=cur;
}
return ret;
}
}
方法1*：简单的层次遍历，使用一个队列实现
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;
Queue<TreeNode> q=new LinkedList<TreeNode>();
q.offer(root);
int lev=0;
ListNode head=new ListNode(-1);
ListNode tmp=head;
while(!q.isEmpty()){
lev++;
int num=q.size(); //区分层的关键语句
for(int i=0;i<num;i++){
if(lev==dep){
tmp.next=new ListNode(q.poll().val);
tmp=tmp.next;
}else{
TreeNode t=q.poll();
if(t.left!=null)
q.offer(t.left);
if(t.right!=null)
q.offer(t.right);
}
}
if(lev==dep) return head.next;
}
return null;
}
}
2*简单DFS
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 {
private ListNode p;
public ListNode getTreeLevel(TreeNode root, int dep) {
if(root==null || dep<=0) return null;
p=new ListNode(-1);
ListNode q=p;
InOrder(root,dep);
return q.next;
}
public void InOrder(TreeNode root,int dep){
if(root==null) return;
if(dep==1){
p.next=new ListNode(root.val);
p=p.next;
return ;
}
InOrder(root.left,dep-1);
InOrder(root.right,dep-1);
}
}