一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 322|回复: 1
收起左侧

[Leetcode] 就是,链表和图题我都有一个不懂的地方leetcode

[复制链接] |试试Instant~ |关注本帖
sy10017667 发表于 2015-11-9 22:44:18 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 sy10017667 于 2015-11-9 23:08 编辑

https://leetcode.com/problems/binary-tree-level-order-traversal/

Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3   / \  9  20    /  \   15   7

return its level order traversal as:

[  [3],  [9,20],  [15,7]]
我用的python
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
我理解,那个TreeNode的构建,是一个类, 类包括3个数据,1个是val left 和right

但是我不懂的是, 为什么在答案的那个类里面, levelorder那个method里,输入值是root
输入的不应该是一个 tree嘛, 链表我也不是很懂,还去把 #删掉了,增加了 getNode, DeleteNode几个方法在链表的类里
自己做不出来,下面是我找到一个答案在尝试理解
def levelOrder(self, root):       # 输入root
        if root is None:          # 如果根节点为空
            return []             #返回空

        nodes = [root]            #当前node
        values = [[root.val]]     #当前 node里的值  为什么两个[]

        while True:                # 这句不懂,while一般不应该是 X== True 或者是 X> n 这种形式吗
            newnodes = []        # 不知道在干什么
            newvalues = []         #不知道在干什么

            for n in nodes:                         # 遍历所有节点
                left, right = n.left, n.right       # 赋值
                if left is not None:                 # 当前节点的左节点为空
                    newnodes.append(left)        #在newnodes 节点里添加 当前节点的左子节点
                    newvalues.append(left.val)   #在newnodes 节点里添加 当前节点的左子节点的值  ,这个也不是很理解
                if right is not None:
                    newnodes.append(right)
                    newvalues.append(right.val)

            if not newvalues:                              如果newvalues的值为假
                return values                              返回values  

            values.append(newvalues)               
            nodes = newnodes                               #语句看得懂,不知道在干嘛


哎呀好难过啊,leetcode好难
顺便问一下, 如果leetcode 说这道题是 BFS, linked list 有没有必要去复习一下概念呢?  用CC150 , expolosed to interviews? or
http://interactivepython.org/runestone/static/pythonds/index.html

stellari 发表于 2015-11-10 13:02:19 | 显示全部楼层
levelOrder是对一个树进行的操作,所以输入理应是一个树,这个逻辑是对的。只不过对树来讲,只要知道了根节点,之后的所有节点都可以被顺次访问到,所以我们用根节点来表示这个树即可,而不需要另外维护这个树中其它节点的地址(特殊需要除外)。这和我们只用单向链表的首元素来代表整个链表是一个道理。

个人意见,如果说到BFS,Linked List你还认为自己有复习概念的必要,那么你就非常有复习的必要。通过你能找到的任何途径都可以,比如我就是在Leetcode上纯看别人代码学会的。如果我是面试官,看到你连BFS都写不出来,是无论如何不会给你正面评价的。希望你多加油。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 10:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表