2020-09-08

今天药忘吃喽~ 2022-12-05 00:55 89阅读 0赞

给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表（比如，若一棵树的深度为 D，则会创建出 D 个链表）。返回一个包含所有深度的链表的数组。

示例：

输入：\[1,2,3,4,5,null,7,8\]

1
       /  \ 
      2    3
     / \    \ 
    4   5    7

/  
8

输出：\[\[1\],\[2,3\],\[4,5,7\],\[8\]\]

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/list-of-depth-lcci  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

下午在宿舍刷题，刷到一道中序遍历的题目，知道要用队列，也知道咋求中序遍历序列，但是就是傻乎乎不知道怎么通过中序遍历求解题目，看了看其他人的题解，恍然大悟，原来只需要两个循环即可，第一个循环判断队列非空，然后记录队列内元素的个数，这里记录的个数也就是该层所有元素的个数，第二个循环里面while(size–)，只取队头的元素，利用队头元素加入新的子树元素到队列中，用完队头的元素就出队，这样一来，在第二个循环里面，是不会碰到下一层的元素（即新加入的元素）的，如此一来，就可以对每一层进行操作惹。下面是具体代码（用C++自带的queue时记得要\#include queue才行）：  
/\*\*

*  Definition for a binary tree node.
 *  struct TreeNode \{
 *      int val;
 *      TreeNode *left;
 *      TreeNode *right;
 *      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 *  \};  
    */  
    /*\*
 *  Definition for singly-linked list.
 *  struct ListNode \{
 *      int val;
 *      ListNode *next;
 *      ListNode(int x) : val(x), next(NULL) {}
 *  \};  
    */  
    using namespace std;  
    class Solution \{  
    public:  
    vector<ListNode*> listOfDepth(TreeNode\* tree) \{  
    queue<TreeNode\*> q;  
    q.push(tree);  
    vector<ListNode\*> result;  
    while(!q.empty())\{  
    int size=q.size();  
    ListNode \*head=new ListNode(0);  
    ListNode \*layerNode=head;  
    while(size–)\{  
    TreeNode \*temp=q.front();  
    q.pop();  
    if(temp->left!=NULL) q.push(temp->left);  
    if(temp->right!=NULL) q.push(temp->right);  
    layerNode->next=new ListNode(temp->val);  
    layerNode=layerNode->next;  
    \}  
    result.push\_back(head->next);  
    delete head;  
    \}  
    return result;  
    \}  
    \};

2020-09-08

发表评论取消回复

还没有评论，来说两句吧...

相关阅读