最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

[百度终极面试]差点挂到二叉树上

XAMPP新闻 admin 546浏览 0评论

hello,我是Johngo!

首先大家周末愉快,然后分享一个点,嗯,就是一个点!

很容易吸收的一个知识点!!!

几天前,来自一个前同事的百度一轮面试题目,不是太难,而且随即就想出来了,还跟面试官因为题目简单开了玩笑。抽空大家不妨也作为饭后甜点看看(^o^)/~

个人感觉这属于那种见过就一定会的那种题目,如果没太接触过这种类似leetcode题目的话,想一下也还是比较简单的。
但是今天还是拿出来,和大家一起分享一下
故事开始→_→

1

题目

要求按照下面的格式将树信息打印出来,看着很是直观的打印结果

drf0052

要求输出格式

A -> 第一行
B C -> 第二行
D E F -> 第三行
G H -> 第四行

就是按照给定的格式进行结点的打印。

2

解决方案

很明显的可以看到,在实现该结果的同时,大致解决思路一定是基于过去咱们看到过的层次遍历的方式

在层次遍历的同时,记录每次换行操作时候的动作

在这所有之前,咱们先给出来结点信息,以便后面清楚的对图中二叉树进行操作

【利用Python看,简单又直观】

class TreeNode:
    def __init__(self, value):
        self.val = value  # 结点值
        self.left = None  # 指向做孩子
        self.right = None  # 指向右孩子

需要回顾层次遍历代码的可以翻到文末,进行了层次遍历的展现,这里有过去用C语言实现的代码

由于题目中要求在打印结点信息的同时,要求给出结点所在行和列的信息

利用层次遍历遍历的特点(重点!重点!重点!在当前层的所有结点元素入队之后,上一层最后一个结点元素才会弹出),初始化两个指针 last 和 cur

  • last 指向上一层最右侧结点
  • cur 是当前结点位置【往队列中输入的结点】

只有当弹出的元素 与 last 指向的结点相同,说明 cur 也遍历到了当前层的最右面。此时,可以令 last = cur

具体细节流程,看下面[长长长长长…]图【可放大】

drf00052

以上,基于给定的树状结构进行了细致的说明,供大家参考。另外个人不太喜欢动图,原因是想要看清楚每一步的时候,不容易控制

对于队列的操作,利用 Python 的 list 数据结构实现的方式如下

# 入队
list.append('A')

# 出队
list.append(0)

下面给出完整代码,并且给出构造树的代码已经层次遍历的代码

3

完整代码

可以直接贴到自己的环境中进行实现哦~

# -*- coding:utf-8 -*-
# !/usr/bin/env python

# 树结点类
class TreeNode:
    def __init__(self, value):
        self.val = value
        self.left = None
        self.right = None

def level_order_traverse(root):
    if not root:
        return
        # 队列queue
    queue = [root]
    while len(queue) > 0:
        node = queue.pop(0)
        print(node.val, end=" ")
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

def level_order_traverse_datail(root):
    last, n_last = root, root
    i = 1
    if not root:
        return
    # 队列queue
    queue = [root]
    while len(queue) > 0:
        node = queue.pop(0)
        print(node.val, end=" ")
        if node.left:
            n_last = node.left
            queue.append(node.left)
        if node.right:
            n_last = node.right
            queue.append(node.right)
        # 当弹出的结点是last指向的结点时,令 last = n_last
        if last is node:
            last = n_last
            print(" -> 第 %d 行" % i)
            i = i + 1

if __name__ == "__main__":
    # 新建节点
    node_A = TreeNode("A")
    node_B = TreeNode("B")
    node_C = TreeNode("C")
    node_D = TreeNode("D")
    node_E = TreeNode("E")
    node_F = TreeNode("F")
    node_G = TreeNode("G")
    node_H = TreeNode("H")

    # 构建二叉树
    #      A
    #    /   \
    #   B     C
    #  /     / \
    # D     E   F
    #      / \
    #     G   H

    node_A.left, node_A.right = node_B, node_C
    node_B.left = node_D
    node_C.left, node_C.right = node_E, node_F
    node_E.left, node_E.right = node_G, node_H

    # 打印结点元素
    print("层次遍历结果:")
    level_order_traverse(node_A)

    print("\n层次遍历结果(打印行号):")
    level_order_traverse_datail(node_A)

好了,今天就先说到这里,这是一个很简单但是很容易被忽略的点,可以加以注意一下。

转载请注明:XAMPP中文组官网 » [百度终极面试]差点挂到二叉树上

您必须 登录 才能发表评论!