0102. 二叉樹的層序遍歷 · ttttt

# 0102. 二叉樹的層序遍歷 ## 題目地址(102. 二叉樹的層序遍歷) <https://leetcode-cn.com/problems/binary-tree-level-order-traversal/> ## 題目描述 ``` <pre class="calibre18">``` 給你一個二叉樹，請你返回其按層序遍歷得到的節點值。（即逐層地，從左到右訪問所有節點）。示例：二叉樹：[3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回其層次遍歷結果： [ [3], [9,20], [15,7] ] ``` ``` ## 前置知識 - 隊列 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路這是一個典型的二叉樹遍歷問題，關于二叉樹遍歷，我總結了一個[專題](https://github.com/azl397985856/leetcode/blob/master/thinkings/binary-tree-traversal.md)，大家可以先去看下那個，然后再來刷這道題。這道題可以借助`隊列`實現，首先把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: ``` <pre class="calibre18">``` /** * @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: ``` <pre class="calibre18">``` /** * 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： ``` <pre class="calibre18">``` # 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 ``` ``` ***復雜度分析*** - 時間復雜度：O(N)O(N)O(N)，其中N為樹中節點總數。 - 空間復雜度：O(N)O(N)O(N)，其中N為樹中節點總數。更多題解可以訪問我的LeetCode題解倉庫：<https://github.com/azl397985856/leetcode> 。目前已經30K star啦。關注公眾號力扣加加，努力用清晰直白的語言還原解題思路，并且有大量圖解，手把手教你識別套路，高效刷題。 ## 擴展實際上這道題方法很多，比如經典的三色標記法。 ## 相關題目 - [103.binary-tree-zigzag-level-order-traversal](103.binary-tree-zigzag-level-order-traversal.html) - [104.maximum-depth-of-binary-tree](104.maximum-depth-of-binary-tree.html) ## 相關專題 - [二叉樹的遍歷](https://github.com/azl397985856/leetcode/blob/master/thinkings/binary-tree-traversal.md)