Alexandra
Alexandra
Jul 27, 2017 · 2 min read

Lintcode69 Binary Tree Level Order Traversal solution 题解

【题目描述】

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

给出一棵二叉树,返回其节点值的层次遍历(逐层从左往右访问)

【题目链接】

www.lintcode.com/en/problem/binary-tree-level-order-traversal/

【题目解析】

对于二叉树的问题,我们第一想到的就是DFS或者BFS, DFS更易于理解代码,如果处理数据量不是很大的话.对于这样的面试题,我建议用DFS来求解.

需要注意的点为:

对于一棵树,如果我们要求每一层的节点,并且存在一个二维数组里,首先我们要建一个二维数组,但是这个二维数组建多大的合适呢?我们就要求出这颗树的深度,根据深度来建立二维数组.

题目要求为从左往右添加,所以我们也就是要先放左边的节点,再放右边的节点.

对于这道题,我们首先就是要用DFS来求出这颗树的高度,之后再用DFS对于每一层遍历,这样节省了空间复杂度.

时间复杂度分析:由于两次DFS是并列的,并没有嵌套,所以我们的时间复杂度为O(n).

【参考答案】

www.jiuzhang.com/solutions/binary-tree-level-order-traversal/

    Alexandra

    Written by

    Alexandra

    Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
    Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
    Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade