首页 > 试题广场 >

输出单层结点

[编程题]输出单层结点
  • 热度指数:16674 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

已知二叉树的根结点指针TreeNode* root以及链表上结点的深度,请设计算法返回一个链表ListNode,该链表代表该深度上所有结点的值,并按树上从左往右的顺序链接,深度不能超过树的高度,且树上结点的值为不大于100000的非负整数。


说明:本题目包含复杂数据结构TreeNode、ListNode,点此查看相关信息
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)

思路

  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);
     }
    
发表于 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)