学会二叉树的层序遍历，可以一口气打完以下十题：

  • 102.二叉树的层序遍历
  • 107.二叉树的层次遍历II
  • 199.二叉树的右视图
  • 637.二叉树的层平均值
  • 429.N叉树的层序遍历
  • 515.在每个树行中找最大值
  • 116.填充每个节点的下一个右侧节点指针
  • 117.填充每个节点的下一个右侧节点指针II
  • 104.二叉树的最大深度
  • 111.二叉树的最小深度

二叉树层序遍历 - 图1

102.二叉树的层序遍历

力扣题目链接

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

二叉树层序遍历 - 图2

思路：

我们之前讲过了三篇关于二叉树的深度优先遍历的文章：

接下来我们再来介绍二叉树的另一种遍历方式：层序遍历。

层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。

需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而是用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。

使用队列实现二叉树广度优先遍历，动画如下：

二叉树层序遍历 - 图3

这样就实现了层序从左到右遍历二叉树。

代码如下：这份代码也可以作为二叉树层序遍历的模板，打十个就靠它了。

C++代码：

  1. class Solution {
  2. public:
  3.     vector<vector<int>> levelOrder(TreeNode* root) {
  4.         queue<TreeNode*> que;
  5.         if (root != NULL) que.push(root);
  6.         vector<vector<int>> result;
  7.         while (!que.empty()) {
  8.             int size = que.size();
  9.             vector<int> vec;
  10.             // 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
  11.             for (int i = 0; i < size; i++) {
  12.                 TreeNode* node = que.front();
  13.                 que.pop();
  14.                 vec.push_back(node->val);
  15.                 if (node->left) que.push(node->left);
  16.                 if (node->right) que.push(node->right);
  17.             }
  18.             result.push_back(vec);
  19.         }
  20.         return result;
  21.     }
  22. };
  1. # 递归法
  2. class Solution {
  3. public:
  4.     void order(TreeNode* cur, vector<vector<int>>& result, int depth)
  5.     {
  6.         if (cur == nullptr) return;
  7.         if (result.size() == depth) result.push_back(vector<int>());
  8.         result[depth].push_back(cur->val);
  9.         order(cur->left, result, depth + 1);
  10.         order(cur->right, result, depth + 1);
  11.     }
  12.     vector<vector<int>> levelOrder(TreeNode* root) {
  13.         vector<vector<int>> result;
  14.         int depth = 0;
  15.         order(root, result, depth);
  16.         return result;
  17.     }
  18. };

python3代码：

  2. class Solution:
  3.     """二叉树层序遍历迭代解法"""
  5.     def levelOrder(self, root: TreeNode) -> List[List[int]]:
  6.         results = []
  7.         if not root:
  8.             return results
  10.         from collections import deque
  11.         que = deque([root])
  13.         while que:
  14.             size = len(que)
  15.             result = []
  16.             for _ in range(size):
  17.                 cur = que.popleft()
  18.                 result.append(cur.val)
  19.                 if cur.left:
  20.                     que.append(cur.left)
  21.                 if cur.right:
  22.                     que.append(cur.right)
  23.             results.append(result)
  25.         return results
  1. # 递归法
  2. class Solution:
  3.     def levelOrder(self, root: TreeNode) -> List[List[int]]:
  4.         res = []
  5.         def helper(root, depth):
  6.             if not root: return []
  7.             if len(res) == depth: res.append([]) # start the current depth
  8.             res[depth].append(root.val) # fulfil the current depth
  9.             if  root.left: helper(root.left, depth + 1) # process child nodes for the next depth
  10.             if  root.right: helper(root.right, depth + 1)
  11.         helper(root, 0)
  12.         return res

java:

  1. // 102.二叉树的层序遍历
  2. class Solution {
  3.     public List<List<Integer>> resList = new ArrayList<List<Integer>>();
  5.     public List<List<Integer>> levelOrder(TreeNode root) {
  6.         //checkFun01(root,0);
  7.         checkFun02(root);
  9.         return resList;
  10.     }
  12.     //DFS--递归方式
  13.     public void checkFun01(TreeNode node, Integer deep) {
  14.         if (node == null) return;
  15.         deep++;
  17.         if (resList.size() < deep) {
  18.             //当层级增加时，list的Item也增加，利用list的索引值进行层级界定
  19.             List<Integer> item = new ArrayList<Integer>();
  20.             resList.add(item);
  21.         }
  22.         resList.get(deep - 1).add(node.val);
  24.         checkFun01(node.left, deep);
  25.         checkFun01(node.right, deep);
  26.     }
  28.     //BFS--迭代方式--借助队列
  29.     public void checkFun02(TreeNode node) {
  30.         if (node == null) return;
  31.         Queue<TreeNode> que = new LinkedList<TreeNode>();
  32.         que.offer(node);
  34.         while (!que.isEmpty()) {
  35.             List<Integer> itemList = new ArrayList<Integer>();
  36.             int len = que.size();
  38.             while (len > 0) {
  39.                 TreeNode tmpNode = que.poll();
  40.                 itemList.add(tmpNode.val);
  42.                 if (tmpNode.left != null) que.offer(tmpNode.left);
  43.                 if (tmpNode.right != null) que.offer(tmpNode.right);
  44.                 len--;
  45.             }
  47.             resList.add(itemList);
  48.         }
  50.     }
  51. }

go:

  1. /**
  2. 102. 二叉树的层序遍历
  3.  */
  4. func levelOrder(root *TreeNode) [][]int {
  5.     res:=[][]int{}
  6.     if root==nil{//防止为空
  7.         return res
  8.     }
  9.     queue:=list.New()
  10.     queue.PushBack(root)
  11.     var tmpArr []int
  12.     for queue.Len()>0 {
  13.         length:=queue.Len()//保存当前层的长度，然后处理当前层（十分重要，防止添加下层元素影响判断层中元素的个数）
  14.         for i:=0;i<length;i++{
  15.             node:=queue.Remove(queue.Front()).(*TreeNode)//出队列
  16.             if node.Left!=nil{
  17.                 queue.PushBack(node.Left)
  18.             }
  19.             if node.Right!=nil{
  20.                 queue.PushBack(node.Right)
  21.             }
  22.             tmpArr=append(tmpArr,node.Val)//将值加入本层切片中
  23.         }
  24.         res=append(res,tmpArr)//放入结果集
  25.         tmpArr=[]int{}//清空层的数据
  26.     }
  27.     return res
  28. }

javascript代码：

  1. var levelOrder = function(root) {
  2.     //二叉树的层序遍历
  3.     let res=[],queue=[];
  4.     queue.push(root);
  5.     if(root===null){
  6.         return res;
  7.     }
  8.     while(queue.length!==0){
  9.         // 记录当前层级节点数
  10.         let length=queue.length;
  11.         //存放每一层的节点 
  12.         let curLevel=[];
  13.         for(let i=0;i<length;i++){
  14.             let node=queue.shift();
  15.             curLevel.push(node.val);
  16.             // 存放当前层下一层的节点
  17.             node.left&&queue.push(node.left);
  18.             node.right&&queue.push(node.right);
  19.         }
  20.         //把每一层的结果放到结果数组
  21.         res.push(curLevel);
  22.     }
  23.     return res;
  24. };

TypeScript：

  1. function levelOrder(root: TreeNode | null): number[][] {
  2.     let helperQueue: TreeNode[] = [];
  3.     let res: number[][] = [];
  4.     let tempArr: number[] = [];
  5.     if (root !== null) helperQueue.push(root);
  6.     let curNode: TreeNode;
  7.     while (helperQueue.length > 0) {
  8.         for (let i = 0, length = helperQueue.length; i < length; i++) {
  9.             curNode = helperQueue.shift()!;
  10.             tempArr.push(curNode.val);
  11.             if (curNode.left !== null) {
  12.                 helperQueue.push(curNode.left);
  13.             }
  14.             if (curNode.right !== null) {
  15.                 helperQueue.push(curNode.right);
  16.             }
  17.         }
  18.         res.push(tempArr);
  19.         tempArr = [];
  20.     }
  21.     return res;
  22. };

Swift：

  1. func levelOrder(_ root: TreeNode?) -> [[Int]] {
  2.     var result = [[Int]]()
  3.     guard let root = root else { return result }
  4.     // 表示一层
  5.     var queue = [root]
  6.     while !queue.isEmpty {
  7.         let count = queue.count
  8.         var subarray = [Int]()
  9.         for _ in 0 ..< count {
  10.             // 当前层
  11.             let node = queue.removeFirst()
  12.             subarray.append(node.val)
  13.             // 下一层
  14.             if let node = node.left { queue.append(node) }
  15.             if let node = node.right { queue.append(node) }
  16.         }
  17.         result.append(subarray)
  18.     }
  20.     return result
  21. }

Rust:

  1. pub fn level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
  2.     let mut ans = Vec::new();
  3.     let mut stack = Vec::new();
  4.     if root.is_none(){
  5.         return ans;
  6.     }
  7.     stack.push(root.unwrap());
  8.     while stack.is_empty()!= true{
  9.         let num = stack.len();
  10.         let mut level = Vec::new();
  11.         for _i in 0..num{
  12.             let tmp = stack.remove(0);
  13.             level.push(tmp.borrow_mut().val);
  14.             if tmp.borrow_mut().left.is_some(){
  15.                 stack.push(tmp.borrow_mut().left.take().unwrap());
  16.             }
  17.             if tmp.borrow_mut().right.is_some(){
  18.                 stack.push(tmp.borrow_mut().right.take().unwrap());
  19.             }
  20.         }
  21.         ans.push(level);
  22.     }
  23.     ans
  24. }

此时我们就掌握了二叉树的层序遍历了，那么如下九道力扣上的题目，只需要修改模板的两三行代码（不能再多了），便可打倒！

107.二叉树的层次遍历 II

力扣题目链接

给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

二叉树层序遍历 - 图4

思路：

相对于102.二叉树的层序遍历，就是最后把result数组反转一下就可以了。

C++代码：

  1. class Solution {
  2. public:
  3.     vector<vector<int>> levelOrderBottom(TreeNode* root) {
  4.         queue<TreeNode*> que;
  5.         if (root != NULL) que.push(root);
  6.         vector<vector<int>> result;
  7.         while (!que.empty()) {
  8.             int size = que.size();
  9.             vector<int> vec;
  10.             for (int i = 0; i < size; i++) {
  11.                 TreeNode* node = que.front();
  12.                 que.pop();
  13.                 vec.push_back(node->val);
  14.                 if (node->left) que.push(node->left);
  15.                 if (node->right) que.push(node->right);
  16.             }
  17.             result.push_back(vec);
  18.         }
  19.         reverse(result.begin(), result.end()); // 在这里反转一下数组即可
  20.         return result;
  22.     }
  23. };

python代码：

  1. class Solution:
  2.     """二叉树层序遍历II迭代解法"""
  4.     def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
  5.         results = []
  6.         if not root:
  7.             return results
  9.         from collections import deque
  10.         que = deque([root])
  12.         while que:
  13.             result = []
  14.             for _ in range(len(que)):
  15.                 cur = que.popleft()
  16.                 result.append(cur.val)
  17.                 if cur.left:
  18.                     que.append(cur.left)
  19.                 if cur.right:
  20.                     que.append(cur.right)
  21.             results.append(result)
  23.         results.reverse()
  24.         return results

Java：

  1. // 107. 二叉树的层序遍历 II
  2. public class N0107 {
  4.     /**
  5.      * 解法：队列，迭代。
  6.      * 层序遍历，再翻转数组即可。
  7.      */
  8.     public List<List<Integer>> solution1(TreeNode root) {
  9.         List<List<Integer>> list = new ArrayList<>();
  10.         Deque<TreeNode> que = new LinkedList<>();
  12.         if (root == null) {
  13.             return list;
  14.         }
  16.         que.offerLast(root);
  17.         while (!que.isEmpty()) {
  18.             List<Integer> levelList = new ArrayList<>();
  20.             int levelSize = que.size();
  21.             for (int i = 0; i < levelSize; i++) {
  22.                 TreeNode peek = que.peekFirst();
  23.                 levelList.add(que.pollFirst().val);
  25.                 if (peek.left != null) {
  26.                     que.offerLast(peek.left);
  27.                 }
  28.                 if (peek.right != null) {
  29.                     que.offerLast(peek.right);
  30.                 }
  31.             }
  32.             list.add(levelList);
  33.         }
  35.         List<List<Integer>> result = new ArrayList<>();
  36.         for (int i = list.size() - 1; i >= 0; i-- ) {
  37.             result.add(list.get(i));
  38.         }
  40.         return result;
  41.     }
  42. }

go:

  1. /**
  2. 107. 二叉树的层序遍历 II
  3.  */
  4. func levelOrderBottom(root *TreeNode) [][]int {
  5.     queue:=list.New()
  6.     res:=[][]int{}
  7.     if root==nil{
  8.         return res
  9.     }
  10.     queue.PushBack(root)
  11.     for queue.Len()>0{
  12.         length:=queue.Len()
  13.         tmp:=[]int{}
  14.         for i:=0;i<length;i++{
  15.             node:=queue.Remove(queue.Front()).(*TreeNode)
  16.             if node.Left!=nil{
  17.                 queue.PushBack(node.Left)
  18.             }
  19.             if node.Right!=nil{
  20.                 queue.PushBack(node.Right)
  21.             }
  22.             tmp=append(tmp,node.Val)
  23.         }
  24.         res=append(res,tmp)
  25.     }
  26.     //反转结果集
  27.     for i:=0;i<len(res)/2;i++{
  28.         res[i],res[len(res)-i-1]=res[len(res)-i-1],res[i]
  29.     }
  30.     return res
  31. }

javascript代码

  1. var levelOrderBottom = function(root) {
  2.     let res=[],queue=[];
  3.     queue.push(root);
  4.     while(queue.length&&root!==null){
  5.         // 存放当前层级节点数组
  6.         let curLevel=[];
  7.         // 计算当前层级节点数量
  8.         let length=queue.length;
  9.         while(length--){
  10.             let node=queue.shift();
  11.             // 把当前层节点存入curLevel数组
  12.             curLevel.push(node.val);
  13.             // 把下一层级的左右节点存入queue队列
  14.             node.left&&queue.push(node.left);
  15.             node.right&&queue.push(node.right);
  16.         }
  17.     // 从数组前头插入值，避免最后反转数组，减少运算时间
  18.         res.unshift(curLevel);
  19.     }
  20.     return res;
  21. };

TypeScript:

  1. function levelOrderBottom(root: TreeNode | null): number[][] {
  2.     let helperQueue: TreeNode[] = [];
  3.     let resArr: number[][] = [];
  4.     let tempArr: number[] = [];
  5.     let tempNode: TreeNode;
  6.     if (root !== null) helperQueue.push(root);
  7.     while (helperQueue.length > 0) {
  8.         for (let i = 0, length = helperQueue.length; i < length; i++) {
  9.             tempNode = helperQueue.shift()!;
  10.             tempArr.push(tempNode.val);
  11.             if (tempNode.left !== null) helperQueue.push(tempNode.left);
  12.             if (tempNode.right !== null) helperQueue.push(tempNode.right);
  13.         }
  14.         resArr.push(tempArr);
  15.         tempArr = [];
  16.     }
  17.     return resArr.reverse();
  18. };

Swift：

  1. func levelOrderBottom(_ root: TreeNode?) -> [[Int]] {
  2.     // 表示一层
  3.     var queue = [TreeNode]()
  4.     if let node = root { queue.append(node) }
  5.     var result = [[Int]]()
  6.     while !queue.isEmpty {
  7.         let count = queue.count
  8.         var subarray = [Int]()
  9.         for _ in 0 ..< count {
  10.             // 当前层
  11.             let node = queue.removeFirst()
  12.             subarray.append(node.val)
  13.             // 下一层
  14.             if let node = node.left { queue.append(node) }
  15.             if let node = node.right { queue.append(node)}
  16.         }
  17.         result.append(subarray)
  18.     }
  20.     return result.reversed()
  21. }

Rust:

  1. pub fn level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
  2.     let mut ans = Vec::new();
  3.     let mut stack = Vec::new();
  4.     if root.is_none(){
  5.         return ans;
  6.     }
  7.     stack.push(root.unwrap());
  8.     while stack.is_empty()!= true{
  9.         let num = stack.len();
  10.         let mut level = Vec::new();
  11.         for _i in 0..num{
  12.             let tmp = stack.remove(0);
  13.             level.push(tmp.borrow_mut().val);
  14.             if tmp.borrow_mut().left.is_some(){
  15.                 stack.push(tmp.borrow_mut().left.take().unwrap());
  16.             }
  17.             if tmp.borrow_mut().right.is_some(){
  18.                 stack.push(tmp.borrow_mut().right.take().unwrap());
  19.             }
  20.         }
  21.         ans.push(level);
  22.     }
  23.     ans
  24. }

199.二叉树的右视图

力扣题目链接

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

二叉树层序遍历 - 图5

思路：

层序遍历的时候，判断是否遍历到单层的最后面的元素，如果是，就放进result数组中，随后返回result就可以了。

C++代码：

  1. class Solution {
  2. public:
  3.     vector<int> rightSideView(TreeNode* root) {
  4.         queue<TreeNode*> que;
  5.         if (root != NULL) que.push(root);
  6.         vector<int> result;
  7.         while (!que.empty()) {
  8.             int size = que.size();
  9.             for (int i = 0; i < size; i++) {
  10.                 TreeNode* node = que.front();
  11.                 que.pop();
  12.                 if (i == (size - 1)) result.push_back(node->val); // 将每一层的最后元素放入result数组中
  13.                 if (node->left) que.push(node->left);
  14.                 if (node->right) que.push(node->right);
  15.             }
  16.         }
  17.         return result;
  18.     }
  19. };

python代码：

  1. class Solution:
  2.     def rightSideView(self, root: TreeNode) -> List[int]:
  3.         if not root:
  4.             return []
  6.         # deque来自collections模块，不在力扣平台时，需要手动写入
  7.         # 'from collections import deque' 导入
  8.         # deque相比list的好处是，list的pop(0)是O(n)复杂度，deque的popleft()是O(1)复杂度
  10.         quene = deque([root])
  11.         out_list = []
  13.         while quene:
  14.             # 每次都取最后一个node就可以了
  15.             node = quene[-1]
  16.             out_list.append(node.val)
  18.             # 执行这个遍历的目的是获取下一层所有的node
  19.             for _ in range(len(quene)):
  20.                 node = quene.popleft()
  21.                 if node.left:
  22.                     quene.append(node.left)
  23.                 if node.right:
  24.                     quene.append(node.right)
  26.         return out_list
  28. # 执行用时：36 ms, 在所有 Python3 提交中击败了89.47%的用户
  29. # 内存消耗：14.6 MB, 在所有 Python3 提交中击败了96.65%的用户

Java:

  1. // 199.二叉树的右视图
  2. public class N0199 {
  3.     /**
  4.      * 解法：队列，迭代。
  5.      * 每次返回每层的最后一个字段即可。
  6.      *
  7.      * 小优化：每层右孩子先入队。代码略。
  8.      */
  9.     public List<Integer> rightSideView(TreeNode root) {
  10.         List<Integer> list = new ArrayList<>();
  11.         Deque<TreeNode> que = new LinkedList<>();
  13.         if (root == null) {
  14.             return list;
  15.         }
  17.         que.offerLast(root);
  18.         while (!que.isEmpty()) {
  19.             int levelSize = que.size();
  21.             for (int i = 0; i < levelSize; i++) {
  22.                 TreeNode poll = que.pollFirst();
  24.                 if (poll.left != null) {
  25.                     que.addLast(poll.left);
  26.                 }
  27.                 if (poll.right != null) {
  28.                     que.addLast(poll.right);
  29.                 }
  31.                 if (i == levelSize - 1) {
  32.                     list.add(poll.val);
  33.                 }
  34.             }
  35.         }
  37.         return list;
  38.     }
  39. }

go:

  2. /**
  3. 199. 二叉树的右视图
  4.  */
  5. func rightSideView(root *TreeNode) []int {
  6.     queue:=list.New()
  7.     res:=[][]int{}
  8.     var finaRes []int
  9.     if root==nil{
  10.         return finaRes
  11.     }
  12.     queue.PushBack(root)
  13.     for queue.Len()>0{
  14.         length:=queue.Len()
  15.         tmp:=[]int{}
  16.         for i:=0;i<length;i++{
  17.             node:=queue.Remove(queue.Front()).(*TreeNode)
  18.             if node.Left!=nil{
  19.                 queue.PushBack(node.Left)
  20.             }
  21.             if node.Right!=nil{
  22.                 queue.PushBack(node.Right)
  23.             }
  24.             tmp=append(tmp,node.Val)
  25.         }
  26.         res=append(res,tmp)
  27.     }
  28.     //取每一层的最后一个元素
  29.     for i:=0;i<len(res);i++{
  30.         finaRes=append(finaRes,res[i][len(res[i])-1])
  31.     }
  32.     return finaRes
  33. }

javascript代码:

  1. var rightSideView = function(root) {
  2.     //二叉树右视图 只需要把每一层最后一个节点存储到res数组
  3.     let res=[],queue=[];
  4.     queue.push(root);
  5.     while(queue.length&&root!==null){
  6.         // 记录当前层级节点个数
  7.         let length=queue.length;
  8.         while(length--){
  9.             let node=queue.shift();
  10.             //length长度为0的时候表明到了层级最后一个节点
  11.             if(!length){
  12.                 res.push(node.val);
  13.             }
  14.             node.left&&queue.push(node.left);
  15.             node.right&&queue.push(node.right);
  16.         }
  17.     }
  18.     return res;
  19. };

TypeScript：

  1. function rightSideView(root: TreeNode | null): number[] {
  2.     let helperQueue: TreeNode[] = [];
  3.     let resArr: number[] = [];
  4.     let tempNode: TreeNode;
  5.     if (root !== null) helperQueue.push(root);
  6.     while (helperQueue.length > 0) {
  7.         for (let i = 0, length = helperQueue.length; i < length; i++) {
  8.             tempNode = helperQueue.shift()!;
  9.             if (i === length - 1) resArr.push(tempNode.val);
  10.             if (tempNode.left !== null) helperQueue.push(tempNode.left);
  11.             if (tempNode.right !== null) helperQueue.push(tempNode.right);
  12.         }
  13.     }
  14.     return resArr;
  15. };

Swift：

  1. func rightSideView(_ root: TreeNode?) -> [Int] {
  2.     // 表示一层
  3.     var queue = [TreeNode]()
  4.     if let node = root { queue.append(node) }
  5.     var result = [Int]()
  6.     while !queue.isEmpty {
  7.         let count = queue.count
  8.         for i in 0 ..< count {
  9.             // 当前层
  10.             let node = queue.removeFirst()
  11.             if i == count - 1 { result.append(node.val) }
  13.             // 下一层
  14.             if let node = node.left { queue.append(node) }
  15.             if let node = node.right { queue.append(node) }
  16.         }
  17.     }
  19.     return result
  20. }

637.二叉树的层平均值

力扣题目链接

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。

二叉树层序遍历 - 图6

思路:

本题就是层序遍历的时候把一层求个总和在取一个均值。

C++代码:

  1. class Solution {
  2. public:
  3.     vector<double> averageOfLevels(TreeNode* root) {
  4.         queue<TreeNode*> que;
  5.         if (root != NULL) que.push(root);
  6.         vector<double> result;
  7.         while (!que.empty()) {
  8.             int size = que.size();
  9.             double sum = 0; // 统计每一层的和
  10.             for (int i = 0; i < size; i++) {
  11.                 TreeNode* node = que.front();
  12.                 que.pop();
  13.                 sum += node->val;
  14.                 if (node->left) que.push(node->left);
  15.                 if (node->right) que.push(node->right);
  16.             }
  17.             result.push_back(sum / size); // 将每一层均值放进结果集
  18.         }
  19.         return result;
  20.     }
  21. };

python代码：

  1. class Solution:
  2.     """二叉树层平均值迭代解法"""
  4.     def averageOfLevels(self, root: TreeNode) -> List[float]:
  5.         results = []
  6.         if not root:
  7.             return results
  9.         from collections import deque
  10.         que = deque([root])
  12.         while que:
  13.             size = len(que)
  14.             sum_ = 0
  15.             for _ in range(size):
  16.                 cur = que.popleft()
  17.                 sum_ += cur.val
  18.                 if cur.left:
  19.                     que.append(cur.left)
  20.                 if cur.right:
  21.                     que.append(cur.right)
  22.             results.append(sum_ / size)
  24.         return results

java:

  2. // 637. 二叉树的层平均值
  3. public class N0637 {
  5.     /**
  6.      * 解法：队列，迭代。
  7.      * 每次返回每层的最后一个字段即可。
  8.      */
  9.     public List<Double> averageOfLevels(TreeNode root) {
  10.         List<Double> list = new ArrayList<>();
  11.         Deque<TreeNode> que = new LinkedList<>();
  13.         if (root == null) {
  14.             return list;
  15.         }
  17.         que.offerLast(root);
  18.         while (!que.isEmpty()) {
  19.             TreeNode peek = que.peekFirst();
  21.             int levelSize = que.size();
  22.             double levelSum = 0.0;
  23.             for (int i = 0; i < levelSize; i++) {
  24.                 TreeNode poll = que.pollFirst();
  26.                 levelSum += poll.val;
  28.                 if (poll.left != null) {
  29.                     que.addLast(poll.left);
  30.                 }
  31.                 if (poll.right != null) {
  32.                     que.addLast(poll.right);
  33.                 }
  34.             }
  35.             list.add(levelSum / levelSize);
  36.         }
  37.         return list;
  38.     }
  39. }

go:

  1. /**
  2. 637. 二叉树的层平均值
  3.  */
  4. func averageOfLevels(root *TreeNode) []float64 {
  5.     res:=[][]int{}
  6.     var finRes []float64
  7.     if root==nil{//防止为空
  8.         return finRes
  9.     }
  10.     queue:=list.New()
  11.     queue.PushBack(root)
  12.     var tmpArr []int
  13.     for queue.Len()>0 {
  14.         length:=queue.Len()//保存当前层的长度，然后处理当前层（十分重要，防止添加下层元素影响判断层中元素的个数）
  15.         for i:=0;i<length;i++{
  16.             node:=queue.Remove(queue.Front()).(*TreeNode)//出队列
  17.             if node.Left!=nil{
  18.                 queue.PushBack(node.Left)
  19.             }
  20.             if node.Right!=nil{
  21.                 queue.PushBack(node.Right)
  22.             }
  23.             tmpArr=append(tmpArr,node.Val)//将值加入本层切片中
  24.         }
  25.         res=append(res,tmpArr)//放入结果集
  26.         tmpArr=[]int{}//清空层的数据
  27.     }
  28.     //计算每层的平均值
  29.     length:=len(res)
  30.     for i:=0;i<length;i++{
  31.         var sum int
  32.         for j:=0;j<len(res[i]);j++{
  33.             sum+=res[i][j]
  34.         }
  35.         tmp:=float64(sum)/float64(len(res[i]))
  36.         finRes=append(finRes,tmp)//将平均值放入结果集合
  37.     }
  38.     return finRes
  39. }

javascript代码：

  1. var averageOfLevels = function(root) {
  2.     //层级平均值
  3.     let res=[],queue=[];
  4.     queue.push(root);
  5.     while(queue.length&&root!==null){
  6.         //每一层节点个数
  7.         let length=queue.length;
  8.         //sum记录每一层的和
  9.         let sum=0;
  10.         for(let i=0;i<length;i++){
  11.             let node=queue.shift();
  12.             sum+=node.val;
  13.             node.left&&queue.push(node.left);
  14.             node.right&&queue.push(node.right);
  15.         }
  16.         //每一层的平均值存入数组res
  17.         res.push(sum/length);
  18.     }
  19.     return res;
  20. };

TypeScript：

  1. function averageOfLevels(root: TreeNode | null): number[] {
  2.     let helperQueue: TreeNode[] = [];
  3.     let resArr: number[] = [];
  4.     let total: number = 0;
  5.     let tempNode: TreeNode;
  6.     if (root !== null) helperQueue.push(root);
  7.     while (helperQueue.length > 0) {
  8.         let length = helperQueue.length;
  9.         for (let i = 0; i < length; i++) {
  10.             tempNode = helperQueue.shift()!;
  11.             total += tempNode.val;
  12.             if (tempNode.left) helperQueue.push(tempNode.left);
  13.             if (tempNode.right) helperQueue.push(tempNode.right);
  14.         }
  15.         resArr.push(total / length);
  16.         total = 0;
  17.     }
  18.     return resArr;
  19. };

Swift：

  1. func averageOfLevels(_ root: TreeNode?) -> [Double] {
  2.     // 表示一层
  3.     var queue = [TreeNode]()
  4.     if let node = root { queue.append(node) }
  5.     var result = [Double]()
  6.     while !queue.isEmpty {
  7.         let count = queue.count
  8.         var sum = 0
  9.         for _ in 0 ..< count {
  10.             // 当前层
  11.             let node = queue.removeFirst()
  12.             sum += node.val
  14.             // 下一层
  15.             if let node = node.left { queue.append(node) }
  16.             if let node = node.right { queue.append(node) }
  17.         }
  18.         result.append(Double(sum) / Double(count))
  19.     }
  21.     return result
  22. }

429.N叉树的层序遍历

力扣题目链接

给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。

例如，给定一个 3叉树 :

二叉树层序遍历 - 图7

返回其层序遍历:

[
[1],
[3,2,4],
[5,6]
]

思路:

这道题依旧是模板题，只不过一个节点有多个孩子了

C++代码:

  1. class Solution {
  2. public:
  3.     vector<vector<int>> levelOrder(Node* root) {
  4.         queue<Node*> que;
  5.         if (root != NULL) que.push(root);
  6.         vector<vector<int>> result;
  7.         while (!que.empty()) {
  8.             int size = que.size();
  9.             vector<int> vec;
  10.             for (int i = 0; i < size; i++) {
  11.                 Node* node = que.front();
  12.                 que.pop();
  13.                 vec.push_back(node->val);
  14.                 for (int i = 0; i < node->children.size(); i++) { // 将节点孩子加入队列
  15.                     if (node->children[i]) que.push(node->children[i]);
  16.                 }
  17.             }
  18.             result.push_back(vec);
  19.         }
  20.         return result;
  22.     }
  23. };

python代码：

  1. class Solution:
  2.     """N叉树的层序遍历迭代法"""
  4.     def levelOrder(self, root: 'Node') -> List[List[int]]:
  5.         results = []
  6.         if not root:
  7.             return results
  9.         from collections import deque
  10.         que = deque([root])
  12.         while que:
  13.             result = []
  14.             for _ in range(len(que)):
  15.                 cur = que.popleft()
  16.                 result.append(cur.val)
  17.                 # cur.children 是 Node 对象组成的列表，也可能为 None
  18.                 if cur.children:
  19.                     que.extend(cur.children)
  20.             results.append(result)
  22.         return results

java:

  2. // 429. N 叉树的层序遍历
  3. public class N0429 {
  4.     /**
  5.      * 解法1：队列，迭代。
  6.      */
  7.     public List<List<Integer>> levelOrder(Node root) {
  8.         List<List<Integer>> list = new ArrayList<>();
  9.         Deque<Node> que = new LinkedList<>();
  11.         if (root == null) {
  12.             return list;
  13.         }
  15.         que.offerLast(root);
  16.         while (!que.isEmpty()) {
  17.             int levelSize = que.size();
  18.             List<Integer> levelList = new ArrayList<>();
  20.             for (int i = 0; i < levelSize; i++) {
  21.                 Node poll = que.pollFirst();
  23.                 levelList.add(poll.val);
  25.                 List<Node> children = poll.children;
  26.                 if (children == null || children.size() == 0) {
  27.                     continue;
  28.                 }
  29.                 for (Node child : children) {
  30.                     if (child != null) {
  31.                         que.offerLast(child);
  32.                     }
  33.                 }
  34.             }
  35.             list.add(levelList);
  36.         }
  38.         return list;
  39.     }
  41.     class Node {
  42.         public int val;
  43.         public List<Node> children;
  45.         public Node() {}
  47.         public Node(int _val) {
  48.             val = _val;
  49.         }
  51.         public Node(int _val, List<Node> _children) {
  52.             val = _val;
  53.             children = _children;
  54.         }
  55.     }
  56. }

go:

  1. /**
  2. 429. N 叉树的层序遍历
  3.  */
  5. func levelOrder(root *Node) [][]int {
  6.     queue:=list.New()
  7.     res:=[][]int{}//结果集
  8.     if root==nil{
  9.         return res
  10.     }
  11.     queue.PushBack(root)
  12.     for queue.Len()>0{
  13.         length:=queue.Len()//记录当前层的数量
  14.         var tmp []int
  15.         for T:=0;T<length;T++{//该层的每个元素：一添加到该层的结果集中；二找到该元素的下层元素加入到队列中，方便下次使用
  16.             myNode:=queue.Remove(queue.Front()).(*Node)
  17.             tmp=append(tmp,myNode.Val)
  18.             for i:=0;i<len(myNode.Children);i++{
  19.                 queue.PushBack(myNode.Children[i])
  20.             }
  21.         }
  22.         res=append(res,tmp)
  23.     }
  24.     return res
  25. }

JavaScript代码：

  1. var levelOrder = function(root) {
  2.     //每一层可能有2个以上,所以不再使用node.left node.right
  3.     let res=[],queue=[];
  4.     queue.push(root);
  5.     while(queue.length&&root!==null){
  6.         //记录每一层节点个数还是和二叉树一致
  7.         let length=queue.length;
  8.         //存放每层节点 也和二叉树一致
  9.         let curLevel=[];
  10.         while(length--){
  11.             let node = queue.shift();
  12.             curLevel.push(node.val);
  13.             //这里不再是 ndoe.left node.right 而是循坏node.children
  14.            for(let item of node.children){
  15.                item&&queue.push(item);
  16.            }
  17.         }
  18.         res.push(curLevel);
  19.     }
  20.     return res;
  21. };

TypeScript:

  1. function levelOrder(root: Node | null): number[][] {
  2.     let helperQueue: Node[] = [];
  3.     let resArr: number[][] = [];
  4.     let tempArr: number[] = [];
  5.     if (root !== null) helperQueue.push(root);
  6.     let curNode: Node;
  7.     while (helperQueue.length > 0) {
  8.         for (let i = 0, length = helperQueue.length; i < length; i++) {
  9.             curNode = helperQueue.shift()!;
  10.             tempArr.push(curNode.val);
  11.             helperQueue.push(...curNode.children);
  12.         }
  13.         resArr.push(tempArr);
  14.         tempArr = [];
  15.     }
  16.     return resArr;
  17. };

Swift：

  1. func levelOrder(_ root: Node?) -> [[Int]] {
  2.     // 表示一层
  3.     var queue = [Node]()
  4.     if let node = root { queue.append(node) }
  5.     var result = [[Int]]()
  6.     while !queue.isEmpty {
  7.         let count = queue.count
  8.         var subarray = [Int]()
  9.         for _ in 0 ..< count {
  10.             // 当前层
  11.             let node = queue.removeFirst()
  12.             subarray.append(node.val)
  13.             // 下一层
  14.             for node in node.children { queue.append(node) }
  15.         }
  16.         result.append(subarray)
  17.     }
  19.     return result
  20. }

515.在每个树行中找最大值

力扣题目链接

您需要在二叉树的每一行中找到最大的值。

二叉树层序遍历 - 图8

思路：

层序遍历，取每一层的最大值

C++代码：

  1. class Solution {
  2. public:
  3.     vector<int> largestValues(TreeNode* root) {
  4.         queue<TreeNode*> que;
  5.         if (root != NULL) que.push(root);
  6.         vector<int> result;
  7.         while (!que.empty()) {
  8.             int size = que.size();
  9.             int maxValue = INT_MIN; // 取每一层的最大值
  10.             for (int i = 0; i < size; i++) {
  11.                 TreeNode* node = que.front();
  12.                 que.pop();
  13.                 maxValue = node->val > maxValue ? node->val : maxValue;
  14.                 if (node->left) que.push(node->left);
  15.                 if (node->right) que.push(node->right);
  16.             }
  17.             result.push_back(maxValue); // 把最大值放进数组
  18.         }
  19.         return result;
  20.     }
  21. };

python代码：

  1. class Solution:
  2.     def largestValues(self, root: TreeNode) -> List[int]:
  3.         if root is None:
  4.             return []
  5.         queue = [root]
  6.         out_list = []
  7.         while queue:
  8.             length = len(queue)
  9.             in_list = []
  10.             for _ in range(length):
  11.                 curnode = queue.pop(0)
  12.                 in_list.append(curnode.val)
  13.                 if curnode.left: queue.append(curnode.left)
  14.                 if curnode.right: queue.append(curnode.right)
  15.             out_list.append(max(in_list))
  16.         return out_list

java代码：

  1. class Solution {
  2.     public List<Integer> largestValues(TreeNode root) {
  3.         if(root == null){
  4.             return Collections.emptyList();
  5.         }
  6.         List<Integer> result = new ArrayList();
  7.         Queue<TreeNode> queue = new LinkedList();
  8.         queue.offer(root);
  9.         while(!queue.isEmpty()){
  10.             int max = Integer.MIN_VALUE;
  11.             for(int i = queue.size(); i > 0; i--){
  12.                TreeNode node = queue.poll();
  13.                max = Math.max(max, node.val);
  14.                if(node.left != null) queue.offer(node.left);
  15.                if(node.right != null) queue.offer(node.right);
  16.             }
  17.             result.add(max);
  18.         } 
  19.         return result;
  20.     }
  21. }

go:

  1. /**
  2. 515. 在每个树行中找最大值
  3.  */
  4. func largestValues(root *TreeNode) []int {
  5.     res:=[][]int{}
  6.     var finRes []int
  7.     if root==nil{//防止为空
  8.         return finRes
  9.     }
  10.     queue:=list.New()
  11.     queue.PushBack(root)
  12.     var tmpArr []int
  13.     //层次遍历
  14.     for queue.Len()>0 {
  15.         length:=queue.Len()//保存当前层的长度，然后处理当前层（十分重要，防止添加下层元素影响判断层中元素的个数）
  16.         for i:=0;i<length;i++{
  17.             node:=queue.Remove(queue.Front()).(*TreeNode)//出队列
  18.             if node.Left!=nil{
  19.                 queue.PushBack(node.Left)
  20.             }
  21.             if node.Right!=nil{
  22.                 queue.PushBack(node.Right)
  23.             }
  24.             tmpArr=append(tmpArr,node.Val)//将值加入本层切片中
  25.         }
  26.         res=append(res,tmpArr)//放入结果集
  27.         tmpArr=[]int{}//清空层的数据
  28.     }
  29.     //找到每层的最大值
  30.     for i:=0;i<len(res);i++{
  31.         finRes=append(finRes,max(res[i]...))
  32.     }
  33.     return finRes
  34. }
  35. func max(vals...int) int {
  36.     max:=int(math.Inf(-1))//负无穷
  37.     for _, val := range vals {
  38.         if val > max {
  39.             max = val
  40.         }
  41.     }
  42.     return max
  43. }

javascript代码：

  1. var largestValues = function(root) {
  2.     //使用层序遍历
  3.     let res=[],queue=[];
  4.     queue.push(root);
  5.     while(root!==null&&queue.length){
  6.         //设置max初始值就是队列的第一个元素
  7.         let max=queue[0].val;
  8.         let length=queue.length;
  9.         while(length--){
  10.             let node = queue.shift();
  11.             max=max>node.val?max:node.val;
  12.             node.left&&queue.push(node.left);
  13.             node.right&&queue.push(node.right);
  14.         }
  15.         //把每一层的最大值放到res数组
  16.         res.push(max);
  17.     }
  18.     return res;
  19. };

TypeScript:

  1. function largestValues(root: TreeNode | null): number[] {
  2.     let helperQueue: TreeNode[] = [];
  3.     let resArr: number[] = [];
  4.     let tempNode: TreeNode;
  5.     let max: number = 0;
  6.     if (root !== null) helperQueue.push(root);
  7.     while (helperQueue.length > 0) {
  8.         for (let i = 0, length = helperQueue.length; i < length; i++) {
  9.             tempNode = helperQueue.shift()!;
  10.             if (i === 0) {
  11.                 max = tempNode.val;
  12.             } else {
  13.                 max = max > tempNode.val ? max : tempNode.val;
  14.             }
  15.             if (tempNode.left) helperQueue.push(tempNode.left);
  16.             if (tempNode.right) helperQueue.push(tempNode.right);
  17.         }
  18.         resArr.push(max);
  19.     }
  20.     return resArr;
  21. };

Swift：

  1. func largestValues(_ root: TreeNode?) -> [Int] {
  2.     // 表示一层
  3.     var queue = [TreeNode]()
  4.     if let node = root { queue.append(node) }
  5.     var result = [Int]()
  6.     while !queue.isEmpty {
  7.         let count = queue.count
  8.         var max = queue[0].val
  9.         for _ in 0 ..< count {
  10.             // 当前层
  11.             let node = queue.removeFirst()
  12.             if node.val > max { max = node.val }
  14.             // 下一层
  15.             if let node = node.left { queue.append(node) }
  16.             if let node = node.right { queue.append(node) }
  17.         }
  18.         result.append(max)
  19.     }
  21.     return result
  22. }

116.填充每个节点的下一个右侧节点指针

力扣题目链接

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

  1. struct Node {
  2.   int val;
  3.   Node *left;
  4.   Node *right;
  5.   Node *next;
  6. }

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

二叉树层序遍历 - 图9

思路:

本题依然是层序遍历，只不过在单层遍历的时候记录一下本层的头部节点，然后在遍历的时候让前一个节点指向本节点就可以了

C++代码：

  1. class Solution {
  2. public:
  3.     Node* connect(Node* root) {
  4.         queue<Node*> que;
  5.         if (root != NULL) que.push(root);
  6.         while (!que.empty()) {
  7.             int size = que.size();
  8.             // vector<int> vec;
  9.             Node* nodePre;
  10.             Node* node;
  11.             for (int i = 0; i < size; i++) {
  12.                 if (i == 0) {
  13.                     nodePre = que.front(); // 取出一层的头结点
  14.                     que.pop();
  15.                     node = nodePre;
  16.                 } else {
  17.                     node = que.front();
  18.                     que.pop();
  19.                     nodePre->next = node; // 本层前一个节点next指向本节点
  20.                     nodePre = nodePre->next;
  21.                 }
  22.                 if (node->left) que.push(node->left);
  23.                 if (node->right) que.push(node->right);
  24.             }
  25.             nodePre->next = NULL; // 本层最后一个节点指向NULL
  26.         }
  27.         return root;
  29.     }
  30. };

java代码：

  1. class Solution {
  2.     public Node connect(Node root) {
  3.     Queue<Node> tmpQueue = new LinkedList<Node>();
  4.     if (root != null) tmpQueue.add(root);
  6.     while (tmpQueue.size() != 0){
  7.         int size = tmpQueue.size();
  9.             Node cur = tmpQueue.poll();
  10.             if (cur.left != null) tmpQueue.add(cur.left);
  11.             if (cur.right != null) tmpQueue.add(cur.right);
  13.         for (int index = 1; index < size; index++){
  14.         Node next = tmpQueue.poll();
  15.         if (next.left != null) tmpQueue.add(next.left);
  16.         if (next.right != null) tmpQueue.add(next.right);
  18.                 cur.next = next;
  19.                 cur = next;
  20.         }
  21.     }
  23.         return root;
  24.     }
  25. }

python代码：

  1. # 层序遍历解法
  2. class Solution:
  3.     def connect(self, root: 'Node') -> 'Node':
  4.         if not root:
  5.             return None
  6.         queue = [root]
  7.         while queue:
  8.             n = len(queue)
  9.             for i in range(n):
  10.                 node = queue.pop(0)
  11.                 if node.left:
  12.                     queue.append(node.left)
  13.                 if node.right:
  14.                     queue.append(node.right)
  15.                 if i == n - 1:
  16.                     break
  17.                 node.next = queue[0]
  18.         return root
  20. # 链表解法
  21. class Solution:
  22.     def connect(self, root: 'Node') -> 'Node':
  23.         first = root
  24.         while first:
  25.             cur = first
  26.             while cur:  # 遍历每一层的节点
  27.                 if cur.left: cur.left.next = cur.right  # 找左节点的next
  28.                 if cur.right and cur.next: cur.right.next = cur.next.left  # 找右节点的next
  29.                 cur = cur.next # cur同层移动到下一节点
  30.             first = first.left  # 从本层扩展到下一层
  31.         return root

JavaScript:

  2. /**
  3.  * // Definition for a Node.
  4.  * function Node(val, left, right, next) {
  5.  *    this.val = val === undefined ? null : val;
  6.  *    this.left = left === undefined ? null : left;
  7.  *    this.right = right === undefined ? null : right;
  8.  *    this.next = next === undefined ? null : next;
  9.  * };
  10.  */
  12. /**
  13.  * @param {Node} root
  14.  * @return {Node}
  15.  */
  16. var connect = function(root) {
  17.     if (root === null) return root;
  18.     let queue = [root];
  19.     while (queue.length) {
  20.         let n = queue.length;
  21.         for (let i=0; i<n; i++) {
  22.             let node = queue.shift();
  23.             if (i < n-1) {
  24.                 node.next = queue[0];
  25.             }
  26.             node.left && queue.push(node.left);
  27.             node.right && queue.push(node.right);
  28.         }
  29.     }
  30.     return root;
  31. };

TypeScript:

  1. function connect(root: Node | null): Node | null {
  2.     let helperQueue: Node[] = [];
  3.     let preNode: Node, curNode: Node;
  4.     if (root !== null) helperQueue.push(root);
  5.     while (helperQueue.length > 0) {
  6.         for (let i = 0, length = helperQueue.length; i < length; i++) {
  7.             if (i === 0) {
  8.                 preNode = helperQueue.shift()!;
  9.             } else {
  10.                 curNode = helperQueue.shift()!;
  11.                 preNode.next = curNode;
  12.                 preNode = curNode;
  13.             }
  14.             if (preNode.left) helperQueue.push(preNode.left);
  15.             if (preNode.right) helperQueue.push(preNode.right);
  16.         }
  17.         preNode.next = null;
  18.     }
  19.     return root;
  20. };

go:

  1. /**
  2. 116. 填充每个节点的下一个右侧节点指针
  3. 117. 填充每个节点的下一个右侧节点指针 II
  4.  */
  6. func connect(root *Node) *Node {
  7.    res:=[][]*Node{}
  8.     if root==nil{//防止为空
  9.         return root
  10.     }
  11.     queue:=list.New()
  12.     queue.PushBack(root)
  13.     var tmpArr []*Node
  14.     for queue.Len()>0 {
  15.         length:=queue.Len()//保存当前层的长度，然后处理当前层（十分重要，防止添加下层元素影响判断层中元素的个数）
  16.         for i:=0;i<length;i++{
  17.             node:=queue.Remove(queue.Front()).(*Node)//出队列
  18.             if node.Left!=nil{
  19.                 queue.PushBack(node.Left)
  20.             }
  21.             if node.Right!=nil{
  22.                 queue.PushBack(node.Right)
  23.             }
  24.             tmpArr=append(tmpArr,node)//将值加入本层切片中
  25.         }
  26.         res=append(res,tmpArr)//放入结果集
  27.         tmpArr=[]*Node{}//清空层的数据
  28.     }
  29.     //遍历每层元素,指定next
  30.     for i:=0;i<len(res);i++{
  31.         for j:=0;j<len(res[i])-1;j++{
  32.             res[i][j].Next=res[i][j+1]
  33.         }
  34.     }
  35.     return root
  36. }

Swift：

  1. func connect(_ root: Node?) -> Node? {
  2.     // 表示一层
  3.     var queue = [Node]()
  4.     if let node = root { queue.append(node) }
  5.     while !queue.isEmpty {
  6.         let count = queue.count
  7.         var current, previous: Node!
  8.         for i in 0 ..< count {
  9.             // 当前层
  10.             if i == 0 {
  11.                 previous = queue.removeFirst()
  12.                 current = previous
  13.             } else {
  14.                 current = queue.removeFirst()
  15.                 previous.next = current
  16.                 previous = current
  17.             }
  19.             // 下一层
  20.             if let node = current.left { queue.append(node) }
  21.             if let node = current.right { queue.append(node) }
  22.         }
  23.         previous.next = nil
  24.     }
  26.     return root
  27. }

117.填充每个节点的下一个右侧节点指针II

力扣题目链接

思路：

这道题目说是二叉树，但116题目说是完整二叉树，其实没有任何差别，一样的代码一样的逻辑一样的味道

C++代码：

  1. class Solution {
  2. public:
  3.     Node* connect(Node* root) {
  4.         queue<Node*> que;
  5.         if (root != NULL) que.push(root);
  6.         while (!que.empty()) {
  7.             int size = que.size();
  8.             vector<int> vec;
  9.             Node* nodePre;
  10.             Node* node;
  11.             for (int i = 0; i < size; i++) {
  12.                 if (i == 0) {
  13.                     nodePre = que.front(); // 取出一层的头结点
  14.                     que.pop();
  15.                     node = nodePre;
  16.                 } else {
  17.                     node = que.front();
  18.                     que.pop();
  19.                     nodePre->next = node; // 本层前一个节点next指向本节点
  20.                     nodePre = nodePre->next;
  21.                 }
  22.                 if (node->left) que.push(node->left);
  23.                 if (node->right) que.push(node->right);
  24.             }
  25.             nodePre->next = NULL; // 本层最后一个节点指向NULL
  26.         }
  27.         return root;
  28.     }
  29. };

Java 代码：

  1. // 二叉树之层次遍历
  2. class Solution {
  3.     public Node connect(Node root) {
  4.         Queue<Node> queue = new LinkedList<>();
  5.         if (root != null) {
  6.             queue.add(root);
  7.         }
  8.         while (!queue.isEmpty()) {
  9.             int size = queue.size();
  10.             Node node = null;
  11.             Node nodePre = null;
  13.             for (int i = 0; i < size; i++) {
  14.                 if (i == 0) {
  15.                     nodePre = queue.poll(); // 取出本层头一个节点
  16.                     node = nodePre;
  17.                 } else {
  18.                     node = queue.poll();
  19.                     nodePre.next = node; // 本层前一个节点 next 指向当前节点
  20.                     nodePre = nodePre.next;
  21.                 }
  22.                 if (node.left != null) {
  23.                     queue.add(node.left);
  24.                 }
  25.                 if (node.right != null) {
  26.                     queue.add(node.right);
  27.                 }
  28.             }
  29.             nodePre.next = null; // 本层最后一个节点 next 指向 null
  30.         }
  31.         return root;
  32.     }
  33. }

python代码：

  1. # 层序遍历解法
  2. class Solution:
  3.     def connect(self, root: 'Node') -> 'Node':
  4.         if not root:
  5.             return None
  6.         queue = [root]
  7.         while queue:  # 遍历每一层
  8.             length = len(queue)
  9.             tail = None # 每一层维护一个尾节点
  10.             for i in range(length): # 遍历当前层
  11.                 curnode = queue.pop(0)
  12.                 if tail:
  13.                     tail.next = curnode # 让尾节点指向当前节点
  14.                 tail = curnode # 让当前节点成为尾节点
  15.                 if curnode.left : queue.append(curnode.left)
  16.                 if curnode.right: queue.append(curnode.right)
  17.         return root
  19. # 链表解法
  20. class Solution:
  21.     def connect(self, root: 'Node') -> 'Node':
  22.         if not root:
  23.             return None
  24.         first = root
  25.         while first:  # 遍历每一层
  26.             dummyHead = Node(None)  # 为下一行创建一个虚拟头节点，相当于下一行所有节点链表的头结点(每一层都会创建)；
  27.             tail = dummyHead  # 为下一行维护一个尾节点指针（初始化是虚拟节点）
  28.             cur = first
  29.             while cur:  # 遍历当前层的节点
  30.                 if cur.left:  # 链接下一行的节点
  31.                     tail.next = cur.left
  32.                     tail = tail.next
  33.                 if cur.right:
  34.                     tail.next = cur.right
  35.                     tail = tail.next
  36.                 cur = cur.next  # cur同层移动到下一节点
  37.             first = dummyHead.next  # 此处为换行操作，更新到下一行
  38.         return root

JavaScript:

  1. /**
  2.  * // Definition for a Node.
  3.  * function Node(val, left, right, next) {
  4.  *    this.val = val === undefined ? null : val;
  5.  *    this.left = left === undefined ? null : left;
  6.  *    this.right = right === undefined ? null : right;
  7.  *    this.next = next === undefined ? null : next;
  8.  * };
  9.  */
  11. /**
  12.  * @param {Node} root
  13.  * @return {Node}
  14.  */
  15. var connect = function(root) {
  16.     if (root === null) {
  17.         return null;
  18.     }
  19.     let queue = [root];
  20.     while (queue.length > 0) {
  21.         let n = queue.length;
  22.         for (let i=0; i<n; i++) {
  23.             let node = queue.shift();
  24.             if (i < n-1) node.next = queue[0];
  25.             if (node.left != null) queue.push(node.left);
  26.             if (node.right != null) queue.push(node.right);
  27.         }
  28.     }
  29.     return root;
  30. };

TypeScript:

  1. function connect(root: Node | null): Node | null {
  2.     let helperQueue: Node[] = [];
  3.     let preNode: Node, curNode: Node;
  4.     if (root !== null) helperQueue.push(root);
  5.     while (helperQueue.length > 0) {
  6.         for (let i = 0, length = helperQueue.length; i < length; i++) {
  7.             if (i === 0) {
  8.                 preNode = helperQueue.shift()!;
  9.             } else {
  10.                 curNode = helperQueue.shift()!;
  11.                 preNode.next = curNode;
  12.                 preNode = curNode;
  13.             }
  14.             if (preNode.left) helperQueue.push(preNode.left);
  15.             if (preNode.right) helperQueue.push(preNode.right);
  16.         }
  17.         preNode.next = null;
  18.     }
  19.     return root;
  20. };

go:

  1. /**
  2. 116. 填充每个节点的下一个右侧节点指针
  3. 117. 填充每个节点的下一个右侧节点指针 II
  4.  */
  6. func connect(root *Node) *Node {
  7.    res:=[][]*Node{}
  8.     if root==nil{//防止为空
  9.         return root
  10.     }
  11.     queue:=list.New()
  12.     queue.PushBack(root)
  13.     var tmpArr []*Node
  14.     for queue.Len()>0 {
  15.         length:=queue.Len()//保存当前层的长度，然后处理当前层（十分重要，防止添加下层元素影响判断层中元素的个数）
  16.         for i:=0;i<length;i++{
  17.             node:=queue.Remove(queue.Front()).(*Node)//出队列
  18.             if node.Left!=nil{
  19.                 queue.PushBack(node.Left)
  20.             }
  21.             if node.Right!=nil{
  22.                 queue.PushBack(node.Right)
  23.             }
  24.             tmpArr=append(tmpArr,node)//将值加入本层切片中
  25.         }
  26.         res=append(res,tmpArr)//放入结果集
  27.         tmpArr=[]*Node{}//清空层的数据
  28.     }
  29.     //遍历每层元素,指定next
  30.     for i:=0;i<len(res);i++{
  31.         for j:=0;j<len(res[i])-1;j++{
  32.             res[i][j].Next=res[i][j+1]
  33.         }
  34.     }
  35.     return root
  36. }

Swift：

  1. func connect(_ root: Node?) -> Node? {
  2.     // 表示一层
  3.     var queue = [Node]()
  4.     if let node = root { queue.append(node) }
  5.     while !queue.isEmpty {
  6.         let count = queue.count
  7.         var current, previous: Node!
  8.         for i in 0 ..< count {
  9.             // 当前层
  10.             if i == 0 {
  11.                 previous = queue.removeFirst()
  12.                 current = previous
  13.             } else {
  14.                 current = queue.removeFirst()
  15.                 previous.next = current
  16.                 previous = current
  17.             }
  19.             // 下一层
  20.             if let node = current.left { queue.append(node) }
  21.             if let node = current.right { queue.append(node) }
  22.         }
  23.         previous.next = nil
  24.     }
  26.     return root
  27. }

104.二叉树的最大深度

力扣题目链接

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：

给定二叉树 [3,9,20,null,null,15,7]，

二叉树层序遍历 - 图10

返回它的最大深度 3 。

思路：

使用迭代法的话，使用层序遍历是最为合适的，因为最大的深度就是二叉树的层数，和层序遍历的方式极其吻合。

在二叉树中，一层一层的来遍历二叉树，记录一下遍历的层数就是二叉树的深度，如图所示：

二叉树层序遍历 - 图11

所以这道题的迭代法就是一道模板题，可以使用二叉树层序遍历的模板来解决的。

C++代码如下：

  1. class Solution {
  2. public:
  3.     int maxDepth(TreeNode* root) {
  4.         if (root == NULL) return 0;
  5.         int depth = 0;
  6.         queue<TreeNode*> que;
  7.         que.push(root);
  8.         while(!que.empty()) {
  9.             int size = que.size();
  10.             depth++; // 记录深度
  11.             for (int i = 0; i < size; i++) {
  12.                 TreeNode* node = que.front();
  13.                 que.pop();
  14.                 if (node->left) que.push(node->left);
  15.                 if (node->right) que.push(node->right);
  16.             }
  17.         }
  18.         return depth;
  19.     }
  20. };

Java：

  1. class Solution {
  2.     public int maxDepth(TreeNode root) {
  3.         if (root == null)   return 0;
  4.         Queue<TreeNode> que = new LinkedList<>();
  5.         que.offer(root);
  6.         int depth = 0;
  7.         while (!que.isEmpty())
  8.         {
  9.             int len = que.size();
  10.             while (len > 0)
  11.             {
  12.                 TreeNode node = que.poll();
  13.                 if (node.left != null)  que.offer(node.left);
  14.                 if (node.right != null) que.offer(node.right);
  15.                 len--;
  16.             }
  17.             depth++;
  18.         }
  19.         return depth;
  20.     }
  21. }

Python：

  1. class Solution:
  2.     def maxDepth(self, root: TreeNode) -> int:
  3.         if root == None:
  4.             return 0
  6.         queue_ = [root]
  7.         result = []
  8.         while queue_:
  9.             length = len(queue_)
  10.             sub = []
  11.             for i in range(length):
  12.                 cur = queue_.pop(0)
  13.                 sub.append(cur.val)
  14.                 #子节点入队列
  15.                 if cur.left: queue_.append(cur.left)
  16.                 if cur.right: queue_.append(cur.right)
  17.             result.append(sub)
  20.         return len(result)

Go：

  1. /**
  2.  * Definition for a binary tree node.
  3.  * type TreeNode struct {
  4.  *     Val int
  5.  *     Left *TreeNode
  6.  *     Right *TreeNode
  7.  * }
  8.  */
  9. func maxDepth(root *TreeNode) int {
  10.     ans:=0
  11.     if root==nil{
  12.         return 0
  13.     }
  14.     queue:=list.New()
  15.     queue.PushBack(root)
  16.     for queue.Len()>0{
  17.         length:=queue.Len()
  18.         for i:=0;i<length;i++{
  19.             node:=queue.Remove(queue.Front()).(*TreeNode)
  20.             if node.Left!=nil{
  21.                 queue.PushBack(node.Left)
  22.             }
  23.             if node.Right!=nil{
  24.                 queue.PushBack(node.Right)
  25.             }
  26.         }
  27.         ans++//记录深度，其他的是层序遍历的板子
  28.     }
  29.     return ans
  30. }

JavaScript：

  1. /**
  2.  * Definition for a binary tree node.
  3.  * function TreeNode(val, left, right) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.left = (left===undefined ? null : left)
  6.  *     this.right = (right===undefined ? null : right)
  7.  * }
  8.  */
  9. /**
  10.  * @param {TreeNode} root
  11.  * @return {number}
  12.  */
  13. var maxDepth = function(root) {
  14.     // 最大的深度就是二叉树的层数
  15.     if (root === null) return 0;
  16.     let queue = [root];
  17.     let height = 0;
  18.     while (queue.length) {
  19.         let n = queue.length;
  20.         height++;
  21.         for (let i=0; i<n; i++) {
  22.             let node = queue.shift();
  23.             node.left && queue.push(node.left);
  24.             node.right && queue.push(node.right);
  25.         }
  26.     }
  27.     return height;
  28. };

TypeScript:

  1. function maxDepth(root: TreeNode | null): number {
  2.     let helperQueue: TreeNode[] = [];
  3.     let resDepth: number = 0;
  4.     let tempNode: TreeNode;
  5.     if (root !== null) helperQueue.push(root);
  6.     while (helperQueue.length > 0) {
  7.         resDepth++;
  8.         for (let i = 0, length = helperQueue.length; i < length; i++) {
  9.             tempNode = helperQueue.shift()!;
  10.             if (tempNode.left) helperQueue.push(tempNode.left);
  11.             if (tempNode.right) helperQueue.push(tempNode.right);
  12.         }
  13.     }
  14.     return resDepth;
  15. };

Swift：

  1. func maxDepth(_ root: TreeNode?) -> Int {
  2.     guard root != nil else { return 0 }
  3.     var depth = 0
  4.     var queue = [TreeNode]()
  5.     queue.append(root!)
  6.     while !queue.isEmpty {
  7.         let count = queue.count
  8.         depth += 1
  9.         for _ in 0 ..< count {
  10.             // 当前层
  11.             let node = queue.removeFirst()
  13.             // 下一层
  14.             if let node = node.left { queue.append(node) }
  15.             if let node = node.right { queue.append(node) }
  16.         }
  17.     }
  19.     return depth
  20. }

111.二叉树的最小深度

力扣题目链接

相对于 104.二叉树的最大深度 ，本题还也可以使用层序遍历的方式来解决，思路是一样的。

需要注意的是，只有当左右孩子都为空的时候，才说明遍历的最低点了。如果其中一个孩子为空则不是最低点

代码如下：（详细注释）

  1. class Solution {
  2. public:
  3.     int minDepth(TreeNode* root) {
  4.         if (root == NULL) return 0;
  5.         int depth = 0;
  6.         queue<TreeNode*> que;
  7.         que.push(root);
  8.         while(!que.empty()) {
  9.             int size = que.size();
  10.             depth++; // 记录最小深度
  11.             for (int i = 0; i < size; i++) {
  12.                 TreeNode* node = que.front();
  13.                 que.pop();
  14.                 if (node->left) que.push(node->left);
  15.                 if (node->right) que.push(node->right);
  16.                 if (!node->left && !node->right) { // 当左右孩子都为空的时候，说明是最低点的一层了，退出
  17.                     return depth;
  18.                 }
  19.             }
  20.         }
  21.         return depth;
  22.     }
  23. };

Java：

  1. class Solution {
  2.     public int minDepth(TreeNode root){
  3.         if (root == null) {
  4.             return 0;
  5.         }
  6.         Queue<TreeNode> queue = new LinkedList<>();
  7.         queue.offer(root);
  8.         int depth = 0;
  9.         while (!queue.isEmpty()){
  10.             int size = queue.size();
  11.             depth++;
  12.             TreeNode cur = null;
  13.             for (int i = 0; i < size; i++) {
  14.                 cur = queue.poll();
  15.                 //如果当前节点的左右孩子都为空，直接返回最小深度
  16.                 if (cur.left == null && cur.right == null){
  17.                     return depth;
  18.                 }
  19.                 if (cur.left != null) queue.offer(cur.left);
  20.                 if (cur.right != null) queue.offer(cur.right);
  21.             }
  22.         }
  23.         return depth;
  24.     }
  25. }

Python 3：

  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, val=0, left=None, right=None):
  4. #         self.val = val
  5. #         self.left = left
  6. #         self.right = right
  7. class Solution:
  8.     def minDepth(self, root: TreeNode) -> int:
  9.         if root == None:
  10.             return 0
  12.         #根节点的深度为1
  13.         queue_ = [(root,1)]
  14.         while queue_:
  15.             cur, depth = queue_.pop(0)
  17.             if cur.left == None and cur.right == None:
  18.                 return depth
  19.             #先左子节点，由于左子节点没有孩子，则就是这一层了
  20.             if cur.left:
  21.                 queue_.append((cur.left,depth + 1))
  22.             if cur.right:
  23.                 queue_.append((cur.right,depth + 1))
  25.         return 0

Go：

  1. /**
  2.  * Definition for a binary tree node.
  3.  * type TreeNode struct {
  4.  *     Val int
  5.  *     Left *TreeNode
  6.  *     Right *TreeNode
  7.  * }
  8.  */
  9. func minDepth(root *TreeNode) int {
  10.     ans:=0
  11.     if root==nil{
  12.         return 0
  13.     }
  14.     queue:=list.New()
  15.     queue.PushBack(root)
  16.     for queue.Len()>0{
  17.         length:=queue.Len()
  18.         for i:=0;i<length;i++{
  19.             node:=queue.Remove(queue.Front()).(*TreeNode)
  20.             if node.Left==nil&&node.Right==nil{//当前节点没有左右节点，则代表此层是最小层
  21.                 return ans+1//返回当前层 ans代表是上一层
  22.             }
  23.             if node.Left!=nil{
  24.                 queue.PushBack(node.Left)
  25.             }
  26.             if node.Right!=nil{
  27.                 queue.PushBack(node.Right)
  28.             }
  29.         }
  30.         ans++//记录层数
  33.     }
  34.     return ans+1
  35. }

JavaScript：

  1. /**
  2.  * Definition for a binary tree node.
  3.  * function TreeNode(val, left, right) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.left = (left===undefined ? null : left)
  6.  *     this.right = (right===undefined ? null : right)
  7.  * }
  8.  */
  9. /**
  10.  * @param {TreeNode} root
  11.  * @return {number}
  12.  */
  13. var minDepth = function(root) {
  14.     if (root === null) return 0;
  15.     let queue = [root];
  16.     let deepth = 0;
  17.     while (queue.length) {
  18.         let n = queue.length;
  19.         deepth++;
  20.         for (let i=0; i<n; i++) {
  21.             let node = queue.shift();
  22.             // 如果左右节点都是null，则该节点深度最小
  23.             if (node.left === null && node.right === null) {
  24.                 return deepth;
  25.             }
  26.             node.left && queue.push(node.left);;
  27.             node.right && queue.push (node.right);
  28.         }
  29.     }
  30.     return deepth;
  31. };

TypeScript:

  1. function minDepth(root: TreeNode | null): number {
  2.     let helperQueue: TreeNode[] = [];
  3.     let resMin: number = 0;
  4.     let tempNode: TreeNode;
  5.     if (root !== null) helperQueue.push(root);
  6.     while (helperQueue.length > 0) {
  7.         resMin++;
  8.         for (let i = 0, length = helperQueue.length; i < length; i++) {
  9.             tempNode = helperQueue.shift()!;
  10.             if (tempNode.left === null && tempNode.right === null) return resMin;
  11.             if (tempNode.left !== null) helperQueue.push(tempNode.left);
  12.             if (tempNode.right !== null) helperQueue.push(tempNode.right);
  13.         }
  14.     }
  15.     return resMin;
  16. };

Swift：

  1. func minDepth(_ root: TreeNode?) -> Int {
  2.     guard root != nil else { return 0 }
  3.     var depth = 0
  4.     var queue = [root!]
  5.     while !queue.isEmpty {
  6.         let count = queue.count
  7.         depth += 1
  8.         for _ in 0 ..< count {
  9.             // 当前层
  10.             let node = queue.removeFirst()
  11.             if node.left == nil, node.right == nil { // 遇到叶子结点则返回
  12.                 return depth
  13.             }
  15.             // 下一层
  16.             if let node = node.left { queue.append(node) }
  17.             if let node = node.right { queue.append(node) }
  18.         }
  19.     }
  20.     return depth
  21. }

总结

二叉树的层序遍历，就是图论中的广度优先搜索在二叉树中的应用，需要借助队列来实现（此时又发现队列的一个应用了）。

来吧，一口气打十个：

  • 102.二叉树的层序遍历
  • 107.二叉树的层次遍历II
  • 199.二叉树的右视图
  • 637.二叉树的层平均值
  • 429.N叉树的前序遍历
  • 515.在每个树行中找最大值
  • 116.填充每个节点的下一个右侧节点指针
  • 117.填充每个节点的下一个右侧节点指针II
  • 104.二叉树的最大深度
  • 111.二叉树的最小深度

致敬叶师傅！

二叉树层序遍历 - 图12