面试题 04.03. 特定深度节点链表
难度中等
给定一棵二叉树,设计一个算法,创建含有某一深度上所有节点的链表(比如,若一棵树的深度为 D,则会创建出 D 个链表)。返回一个包含所有深度的链表的数组。
示例:
思路1.0:
(1)这不就是层次遍历嘛。
(2)创建一个队列Que,配合变量len来判断处于当前层的节点有哪些。
代码1.0:
复制代码
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57/** * 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) {} * }; */ class Solution { public: vector<ListNode*> listOfDepth(TreeNode* tree) { //用于存储每层节点的队列 queue<TreeNode> que; //存储结果的vec vector<ListNode*> rst; //根节点进入 if (tree != NULL) { que.push(*tree); } while (!que.empty()) { //每层的结果用链表存储 ListNode* head = new ListNode(0); ListNode* p1 = head, * p2 = NULL; //用len记录当前层的数目 int len = que.size(); //遍历当前层的所有元素 for (int i = 0; i < len; ++i) { auto nextTN = que.front(); //实时更新每层的ListNode p2 = new ListNode(nextTN.val); p1->next = p2; p1 = p2; //将当前层所有元素的chidren存入队列 if (nextTN.left != NULL) que.push(*nextTN.left); if (nextTN.right != NULL) que.push(*nextTN.right); que.pop(); } p1->next = NULL; rst.push_back(head->next); } return rst; } };
链表的创建又有点忘了,最后AC的成绩还不错啊哈哈哈。
最后
以上就是自由大树最近收集整理的关于PigyChan_LeetCode 面试题 04.03. 特定深度节点链表的全部内容,更多相关PigyChan_LeetCode内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复