LeetCode面试题 04.03. 特定深度节点链表

1
2
3
4
5
6
7
8
      1
     /   
    2    3
   /      
  4   5    7  
 / 
8

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<ListNode*> listOfDepth(TreeNode* tree) {
        if(!tree) return vector<ListNode*>();//空树判断
        vector<ListNode*> v;//链表头节点指针类型的vector(返回值)
        queue<TreeNode*>q;//队列，用于存储每一层的值
        q.push(tree);//初始化，将root放入队列
        while(!q.empty()){//退出条件：队列为空
            ListNode*head=new ListNode();//创建空的头节点
            ListNode*k=head;//创建指针k指向头节点
            int qsize=q.size();//获得当前队列元素个数
            for(int i=0;i<qsize;i++){//遍历当前队列每一个元素                
                TreeNode*p=q.front();//用p存储队列的头一个节点
                q.pop();//将头节点剔除
                k->next=new ListNode(p->val);//给链表添加下一个节点并赋值
                k=k->next;//k指针向后移
                if(p->left) q.push(p->left);//若该TreeNode有左孩子，将左孩子加入队列
                if(p->right) q.push(p->right);//同上

            }
            v.push_back(head->next);//将该层的链表放入vector
        }
        return v;//遍历完所有层返回

    }
};

1
2
3
int qsize=q.size();//获得当前队列元素个数
for(int i=0;i<qsize;i++){//遍历当前队列每一个元素 

1
2
for(int i=q.size();i>0;i--)