题目地址
https://leetcode.com/problems/binary-tree-level-order-traversal/description/
题目描述
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,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
思路
这道题可以借助队列
实现,首先把root入队,然后入队一个特殊元素Null(来表示每层的结束)。
然后就是while(queue.length), 每次处理一个节点,都将其子节点(在这里是left和right)放到队列中。
然后不断的出队, 如果出队的是null,则表式这一层已经结束了,我们就继续push一个null。
如果不入队特殊元素Null来表示每层的结束,则在while循环开始时保存当前队列的长度,以保证每次只遍历一层(参考下面的C++ Code)。
如果采用递归方式,则需要将当前节点,当前所在的level以及结果数组传递给递归函数。在递归函数中,取出节点的值,添加到level参数对应结果数组元素中(参考下面的C++ Code 或 Python Code)。
关键点解析
-
队列
-
队列中用Null(一个特殊元素)来划分每层
-
树的基本操作- 遍历 - 层次遍历(BFS)
-
注意塞入null的时候,判断一下当前队列是否为空,不然会无限循环
代码
- 语言支持:JS,C++,Python3
Javascript Code:
/* * @lc app=leetcode id=102 lang=javascript * * [102] Binary Tree Level Order Traversal * * https://leetcode.com/problems/binary-tree-level-order-traversal/description/ * * algorithms * Medium (47.18%) * Total Accepted: 346.4K * Total Submissions: 731.3K * Testcase Example: '[3,9,20,null,null,15,7]' * * 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,null,null,15,7], * * * 3 * / \ * 9 20 * / \ * 15 7 * * * * return its level order traversal as: * * [ * [3], * [9,20], * [15,7] * ] * * */ /** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @return {number[][]} */ var levelOrder = function(root) { if (!root) return []; const items = []; // 存放所有节点 const queue = [root, null]; // null 简化操作 let levelNodes = []; // 存放每一层的节点 while (queue.length > 0) { const t = queue.shift(); if (t) { levelNodes.push(t.val) if (t.left) { queue.push(t.left); } if (t.right) { queue.push(t.right); } } else { // 一层已经遍历完了 items.push(levelNodes); levelNodes = []; if (queue.length > 0) { queue.push(null) } } } return items; };
C++ Code:
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ // 迭代 class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { auto ret = vector<vector<int>>(); if (root == nullptr) return ret; auto q = vector<TreeNode*>(); q.push_back(root); auto level = 0; while (!q.empty()) { auto sz = q.size(); ret.push_back(vector<int>()); for (auto i = 0; i < sz; ++i) { auto t = q.front(); q.erase(q.begin()); ret[level].push_back(t->val); if (t->left != nullptr) q.push_back(t->left); if (t->right != nullptr) q.push_back(t->right); } ++level; } return ret; } }; // 递归 class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> v; levelOrder(root, 0, v); return v; } private: void levelOrder(TreeNode* root, int level, vector<vector<int>>& v) { if (root == NULL) return; if (v.size() < level + 1) v.resize(level + 1); v[level].push_back(root->val); levelOrder(root->left, level + 1, v); levelOrder(root->right, level + 1, v); } };
Python Code:
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def levelOrder(self, root: TreeNode) -> List[List[int]]: """递归法""" if root is None: return [] result = [] def add_to_result(level, node): """递归函数 :param level int 当前在二叉树的层次 :param node TreeNode 当前节点 """ if level > len(result) - 1: result.append([]) result[level].append(node.val) if node.left: add_to_result(level+1, node.left) if node.right: add_to_result(level+1, node.right) add_to_result(0, root) return result
相关题目
- 103.binary-tree-zigzag-level-order-traversal
- 104.maximum-depth-of-binary-tree
我正在尝试解决此问题https://oj.leetcode.com/problems/binary-tree-preorder-traversal/,即使用递归解决方案进行预遍历。编辑:整个代码:import java.util.ArrayList; import java.util.List; public class Solution { public …