程序员面试金典

    技术2022-07-13  69

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

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

    示例:

    输入:[1,2,3,4,5,null,7,8] 1 / \ 2 3 / \ \ 4 5 7 / 8 输出:[[1],[2,3],[4,5,7],[8]]

    思路:

    完整代码实现:

    class Solution { public: vector<ListNode*> listOfDepth(TreeNode* tree) { if(tree==nullptr)return vector<ListNode*>(); vector<ListNode*> v; queue<TreeNode*> q; q.push(tree); while(!q.empty()){ ListNode *h = new ListNode(); ListNode *k=h; for(int i=q.size(); i>0; i--){ TreeNode *p = q.front(); q.pop(); k->next = new ListNode(p->val); k = k->next; if(p->left)q.push(p->left); if(p->right)q.push(p->right); } v.push_back(h->next); } return v; } };
    Processed: 0.013, SQL: 9