首页 > 试题广场 >

输出单层结点

[编程题]输出单层结点

热度指数：16731 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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

说明：本题目包含复杂数据结构TreeNode、ListNode，点此查看相关信息

算法知识视频讲解

Python

华科平凡

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)

Python

Yannyezixin

思路：

类似广度优先搜索二叉树，遍历dep层时，我们已经遍历了dep - 1了，也就是说，我们只要记住遍历到哪一层就可以了。可以借助一个队列实现广搜，遍历到dep层时链接链表并结束遍历

    def getTreeLevel(self, root, dep):
        if not root:
            return None
        
        queue = []
        queue.append((1, root))
        head = p = ListNode(-1)
        
        while queue:
            top = queue.pop(0)
            if top[0] == dep:
                node = ListNode(top[1].val)
                p.next = node
                p = p.next
            else:
                if top[1].left:
                	queue.append((top[0] + 1, top[1].left))
                if top[1].right:
                    queue.append((top[0] + 1, top[1].right))
                    
        return head.next

发表于 2016-08-02 21:59:15 回复(0)