已知二叉树的根结点指针TreeNode* root以及链表上结点的深度，请设计算法返回一个链表ListNode，该链表代表该深度上所有结点的值，并按树上从左往右的顺序链接，深度不能超过树的高度，且树上结点的值为不大于100000的非负整数。
[编程题]输出单层结点
public class TreeLevel {
ListNode ln = new ListNode(-1);
ListNode p = ln;
public ListNode getTreeLevel(TreeNode root, int dep) {
// write code here
if (root == null || dep <= 0)
return null;
if (dep == 1) {
p.next = new ListNode(root.val);
p = p.next;
} else {
getTreeLevel(root.left, dep - 1);
getTreeLevel(root.right, dep - 1);
}
return ln.next;
}
}
发表于 2016-03-19 13:23:10
回复(3)
《程序员面试金典》--编程题目详解：
<方法1>：层次遍历
这个题目的意思就是输出二叉树的某一层的所有元素，这个首先想到的是层次遍历，层次遍历最简单的方法就是用队列实现，我们传统的层次遍历方法是可以输出所有元素，那么如何区分相邻两层之间的元素呢？
其实我们可以用两个整数变量line1，line2来记录相邻两层的元素个数，其中line1代表出栈那一层留下的元素个数，line2代表下一层进栈元素的个数，每当line1为0的时候，说明上一层已经全部出栈，下一层已经全部入栈，那么层次遍历层数就加一，这个时候将line2的值复制给line1，line2=0，当遍历到第dep层的时候，便把那一层的所有元素输出，停止遍历。
代码实现如下：
class TreeLevel {
public:
ListNode* getTreeLevel(TreeNode* root, int dep) {
// write code here
if(dep<=0||root==NULL)
return NULL;
ListNode* list=new ListNode(-1);
ListNode* listHead=list;
queue<TreeNode*> qu;
qu.push(root);
int lines1=1,lines2=0,num=1;
while(!qu.empty())
{
if(num==dep)
{
for(int i=0;i<lines1;i++)
{
TreeNode* root1=qu.front();
list->next=new ListNode(root1->val);
list=list->next;
qu.pop();
}
return listHead->next;
}
TreeNode* root1=qu.front();
if(root1->left)
{
qu.push(root1->left);
lines2++;
}
if(root1->right)
{
qu.push(root1->right);
lines2++;
}
qu.pop();
if(--lines1==0)
{
lines1=lines2;
lines2=0;
num++;
}
}
return listHead->next;
}
};
<方法2>：递归遍历
其实也可以用递归遍历实现，刚开始为深度为dep，每往下递归一层，则深度减一（dep=dep-1），当dep==1的时候，便输出那个元素，如果先递归左子树，那么则实现从左到右打印，如果先递归右子树，则实现从右往左打印。
程序代码如下：
class TreeLevel {
public:
ListNode* getTreeLevel(TreeNode* root, int dep) {
// write code here
ListNode* list=new ListNode(-1);
ListNode* listHead=list;
get1(root,list,dep);
return listHead->next;
}
void get1(TreeNode* root,ListNode* &list,int dep)
{
if(dep<=0||root==NULL)
return;
if(dep==1)
{
ListNode* listnext=new ListNode(root->val);
list->next=listnext;
list=list->next;
return ;
}
get1(root->left,list,dep-1);
get1(root->right,list,dep-1);
}
};
发表于 2015-10-23 19:06:08
回复(8)
有点诡异 用递归
class TreeLevel {
public:
ListNode* getTreeLevel(TreeNode* root, int dep) {
// write code here
if(root == NULL || dep <= 0) return NULL;
p = new ListNode(-1);
ListNode* head = p;
InOrder(root, dep);
return head->next;
}
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);
}
private:
ListNode *p;
};
发表于 2015-07-30 10:06:40
回复(2)
//看没有用Java做的，，分享一个Java的吧
//思路是使用层次遍历，当遍历到该层时，dep--，此时，队列中的即是dep层的节点
import java.util.*;
public class TreeLevel {
public ListNode getTreeLevel(TreeNode root, int dep) {
// write code here
if(root==null) return null;
Queue<TreeNode> que=new LinkedList<TreeNode>();
int len=0,i;
que.add(root);
while(dep>1&&!que.isEmpty()){
len=que.size();
for(i=0;i<len;i++){
TreeNode p=que.poll();
if(p.left != null)
que.add(p.left);
if(p.right != null)
que.add(p.right);
}
dep--;
}
ListNode res=new ListNode(que.poll().val);
ListNode tem=res;
while(!que.isEmpty()){
tem.next=new ListNode(que.poll().val);
tem=tem.next;
}
return res;
}
}
发表于 2017-04-02 15:14:40
回复(0)
思路
- 要获取指定深度的节点，只需在二叉树的先序遍历过程中加上深度值即可。
- 由于先序遍历是先访问左孩子、再访问右孩子，所以某一层的左孩子一定先访问到，右孩子一定后访问到。
代码
只要在先序遍历函数上加上两个参数即可：
- 当前深度；
-
目标深度 若当前深度和目标深度一致时，将当前节点输出，并直接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); }
发表于 2017-03-30 21:28:43
回复(2)
//层序遍历找到深度指向的层数，将其val存入链表
class TreeLevel {
public:
ListNode* getTreeLevel(TreeNode* root, int dep) {
// write code here
ListNode *pRoot = new ListNode(-1);
ListNode *pNode = pRoot;
if (root == NULL)
return pRoot;
queue<TreeNode*> Node;
Node.push(root);
int count = 1;
vector<int> Data;
while (!Node.empty())
{
int Index = 0;
int len = Node.size();
vector<int> data;
while (Index++ < len)
{
TreeNode *pNode = Node.front();
Node.pop();
data.push_back(pNode->val);
if (pNode->left != NULL)
Node.push(pNode->left);
if (pNode->right != NULL)
Node.push(pNode->right);
}
if (count == dep)
{
Data = data;
break;
}
count++;
}
for (int i = 0; i < Data.size(); i++)
{
ListNode *p = new ListNode(Data[i]);
pNode->next = p;
pNode = pNode->next;
}
return pRoot->next;
}
};
发表于 2015-09-29 16:25:06
回复(1)
public class TreeLevel {
public ListNode getTreeLevel(TreeNode root, int dep) {
if (root == null) {
return null;
}
ListNode head = new ListNode(0);
ListNode p = head;
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
int d = 0;
while (!queue.isEmpty()) {
d++;
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.remove();
if (d == dep) {
p.next = new ListNode(node.val);
p = p.next;
}
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
if (d == dep) {
break;
}
}
return head.next;
}
}
发表于 2016-09-09 16:09:36
回复(0)
一个队列广搜，到达第dep层后队列所存即为该层结点。
class TreeLevel {
public:
ListNode* getTreeLevel(TreeNode* root, int dep) {
// write code here
queue<TreeNode *> q;
q.push(root);
int current_wid = 1, next_wid = 0, d = 1;
while(!q.empty())
{
if(current_wid == 0)
{
d++;
current_wid = next_wid;
next_wid = 0;
}
if(d == dep)
break;
TreeNode *temp = q.front();
q.pop();
current_wid--;
if(temp->left != NULL)
{
q.push(temp->left);
next_wid++;
}
if(temp->right != NULL)
{
q.push(temp->right);
next_wid++;
}
}
if(q.empty())
return new ListNode(-1);
int value = q.front()->val;
q.pop();
ListNode *head = new ListNode(value), * node;
node = head;
while(!q.empty())
{
node->next = new ListNode(q.front()->val);
q.pop();
node = node->next;
}
return head;
}
};
发表于 2016-05-02 14:17:23
回复(0)
思路
利用两个队列来进行层次遍历，当进行到第dep层时创建链表。
代码
class TreeLevel {
public:
ListNode* getTreeLevel(TreeNode* root, int dep) {
if(root == nullptr || dep <= 0){
return nullptr;
}//if
// 头结点
ListNode *head = new ListNode(-1);
ListNode *p = head;
// 队列 层次遍历
queue<TreeNode*> curQueue;
curQueue.push(root);
queue<TreeNode*> nextQueue;
int level = 1;
while(!curQueue.empty()){
while(!curQueue.empty()){
TreeNode *node = curQueue.front();
curQueue.pop();
// 某一深度上所有结点的链表
if(level == dep){
p->next = new ListNode(node->val);
p = p->next;
}//if
if(node->left){
nextQueue.push(node->left);
}//if
if(node->right){
nextQueue.push(node->right);
}//if
}//while
swap(curQueue,nextQueue);
if(level == dep){
return head->next;
}//if
++level;
}//while
return nullptr;
}
};
发表于 2015-08-19 20:57:18
回复(0)
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class TreeLevel {
public:
ListNode* getTreeLevel(TreeNode* root, int dep) {
// corner case
if (!root) return nullptr;
deque<TreeNode*> q{{root}};
ListNode dummy(-1), *tail = &dummy;
int level = 1;
while (not q.empty() && level <= dep) {
size_t s = q.size();
while (s--) {
auto curr = q.front(); q.pop_front();
if (level == dep) {
tail = tail->next = new ListNode(curr->val);
continue;
}
if (curr->left) q.push_back(curr->left);
if (curr->right) q.push_back(curr->right);
}
++level;
}
return dummy.next;
}
};
发表于 2021-07-09 13:21:46
回复(0)
我这个应该挺好理解
ListNode head = new ListNode(0);
ListNode tmp = head;
public ListNode getTreeLevel(TreeNode root, int dep) {
// write code here
get(root, 1, dep);
return head.next;
}
public void get(TreeNode root, int curDep, int dep){
if(curDep == dep){
tmp.next = new ListNode(root.val);
tmp = tmp.next;
return;
}
if(root.left != null){
get(root.left, curDep +1, dep);
}
if(root.right != null){
get(root.right, curDep +1, dep);
}
}
发表于 2020-07-07 10:57:41
回复(0)
//可以采用前序遍历，到达一定深度就开始存储节点值
class TreeLevel {
public:
ListNode* getTreeLevel(TreeNode* root, int dep) {
if(root==nullptr) return nullptr;
ListNode *head=new ListNode(-1);
ListNode *p=head;
int count=1;
seek(root,p,count,dep);
return head->next;
}
private:
void seek(TreeNode *root,ListNode *&ptr,int cnt,int dep)
{
if(cnt>dep||root==nullptr) return ;
if(cnt==dep)
{
ListNode *temp=new ListNode(root->val);
ptr->next=temp;
ptr=temp;
return ;
}
seek(root->left,ptr,cnt+1,dep);
seek(root->right,ptr,cnt+1,dep);
return ;
}
};
//PS：也可以采用层次遍历
class TreeLevel {
public:
ListNode* getTreeLevel(TreeNode* root, int dep) {
// write code here
if(root==nullptr||dep==0) return nullptr;
ListNode *head=new ListNode(-1);
ListNode *p=head;
queue<TreeNode*>q;
q.push(root);
int cnt=0;
while(!q.empty())
{
int size=q.size();
++cnt;
if(cnt>dep) break;
for(int i=0;i<size;++i)
{
TreeNode *front=q.front();
q.pop();
if(cnt==dep)
{
ListNode *temp=new ListNode(front->val);
p->next=temp;
p=temp;
}
if(front->left!=nullptr)
q.push(front->left);
if(front->right!=nullptr)
q.push(front->right);
}
}
return head->next;
}
};
编辑于 2019-05-04 11:30:10
回复(0)
层次遍历
class TreeLevel {
public:
ListNode* getTreeLevel(TreeNode* root, int dep) {
if (!root) { return nullptr; }
queue<TreeNode*> Q;
ListNode* p = new ListNode(0);
ListNode* res = p;
Q.push(root);
int h = 0;
while (!Q.empty()) {
int n = Q.size();
++h;
if (h > dep) { break; }
while (n) {
TreeNode* node = Q.front();
Q.pop();
if (dep == h) {
p->next = (ListNode*)node;
p = p->next;
}
if (node->left) {
Q.push(node->left);
}
if (node->right) {
Q.push(node->right);
}
--n;
}
}
p->next = nullptr;
res = res->next;
return res;
}
};
运行时间：4ms
占用内存：592k
发表于 2018-12-25 23:28:21
回复(0)
python solution
先遍历，再创建链表。
class TreeLevel:
def getTreeLevel(self, root, dep):
if not root: return
nodeStack = [root]
res = []
while nodeStack:
res.append([i.val for i in nodeStack])
nodeStack = [i for node in nodeStack for i in (node.left, node.right) if i]
dummy = ListNode(0)
pre = dummy
for i in res[dep - 1]:
node = ListNode(i)
pre.next = node
pre = pre.next
return dummy.next
发表于 2017-10-31 16:03:50
回复(0)
非递归的方法，思路清晰很容易看懂。
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;
}
}
发表于 2017-10-19 10:41:46
回复(0)
// 头铁的方法
public class TreeLevel {
public ListNode getTreeLevel(TreeNode root, int dep) {
// write code here
ListNode head = null;
if(root == null || dep < 0){
return head;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
int depth = 1;
int count = 0;
int children = 1;
queue.offer(root);
while(!queue.isEmpty()){
TreeNode temp = queue.poll();
if(depth == dep){
ListNode cur = new ListNode(temp.val);
if(head == null){
head = cur;
}else{
cur.next = head;
head = cur;
}
}
if(depth == dep + 1){
break;
}
count++;
//需要head为最左边元素就从右往左添加队列。
if(temp.right != null){
queue.offer(temp.right);
}
if(temp.left != null){
queue.offer(temp.left);
}
if(count == children){
children = queue.size();
count = 0;
depth++;
}
}
return head;
}
}
发表于 2017-08-28 16:18:39
回复(0)
// BFS public ListNode getTreeLevel(TreeNode root, int dep) { if(root!=null&&dep==1) return new ListNode(root.val); if(root==null||dep<=0) return null; ListNode head = null; ListNode last = null; Queue<NodeAndHeight> queue = new LinkedList<>(); queue.offer(new NodeAndHeight(root,1)); // 根节点入队 while(!queue.isEmpty()){ NodeAndHeight nah = queue.poll(); if(nah.height==dep){ if(head==null){ head = new ListNode(nah.node.val); last = head; }else{ last.next = new ListNode(nah.node.val); last = last.next; } } if(nah.node.left!=null&&nah.height<dep){ queue.offer(new NodeAndHeight(nah.node.left,nah.height+1)); } if(nah.node.right!=null&&nah.height<dep){ queue.offer(new NodeAndHeight(nah.node.right,nah.height+1)); } } return head; } class NodeAndHeight{ TreeNode node; int height; NodeAndHeight(TreeNode node,int height){ this.node = node; this.height = height; } }
发表于 2017-08-10 16:29:18
回复(0)
层次遍历
public static ListNode getTreeLevel(TreeNode root, int dep) {
LinkedList<TreeNode> link = new LinkedList<TreeNode>();
ListNode p = null;
ListNode list = new ListNode(-1); //list指向头节点
p = list;
link.addLast(root);
link.addLast(null); //用null来表示每一层的分隔
while (!link.isEmpty()){
root = link.removeFirst();
if (root == null){
dep--; //下降一层
if (!link.isEmpty())
link.addLast(null);
continue;
}
if (dep == 1){
if (root != null){
p.next = new ListNode(root.val);
p = p.next;
}
}
if (root.left != null){
link.addLast(root.left);
}
if (root.right != null){
link.addLast(root.right);
}
}
return list.next;
}
发表于 2017-07-30 22:52:48
回复(0)
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;
}
}
编辑于 2017-06-30 10:31:57
回复(0)
//深度遍历，不需要使用队列，递归的顺序即为从左至右
public class TreeLevel {
ListNode head = new ListNode(-1);
ListNode p = head;
public ListNode getTreeLevel(TreeNode root, int dep) {
// write code here
traversal(root, dep);
return head.next;
}
private void traversal(TreeNode root, int dep){
if(root != null) {
if(dep == 1) {
p.next = new ListNode(root.val);
p = p.next;
}
traversal(root.left, dep - 1);
traversal(root.right, dep - 1);
}
}
}
发表于 2017-06-28 21:46:44
回复(0)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
