👊7.填充每个节点的下一个右侧节点指针
给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
题目链接：填充每个节点的下一个右侧节点指针https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/
这道题稍难与前面的几道题，不过也不难看出是层序遍历的思想，只不过我们需要每次保存住上一个遍历的结点，然后去让它的next属性指向当前结点，大家通过代码即可理解。
class Solution { public Node connect(Node root) { dfs(root); return root; } public void dfs(Node root){ if(root==null) return; Queue<Node> queue=new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()){ Node a=queue.poll(); int len=queue.size(); if(a.left!=null) queue.offer(a.left); if(a.right!=null) queue.offer(a.right); while(len>0){ Node b=queue.poll(); if(b.left!=null) queue.offer(b.left); if(b.right!=null) queue.offer(b.right); a.next=b; a=a.next; len--; } } } }
👊8.填充每个节点的下一个右侧节点指针||
给定一个二叉树（上一题是完美）
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
题目链接：填充每个节点的下一个右侧节点指针||https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii/
这道题和上一道题唯一的区别就是上题是给的完美二叉树，这道题给的是非完美的二叉树。但是！有区别吗？根本不影响我们上一道题的代码实现，同样的代码同样适用
广度优先搜索做法（层序遍历）
class Solution { public Node connect(Node root) { dfs(root); return root; } public void dfs(Node root){ if(root==null) return; Queue<Node> queue=new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()){ Node a=queue.poll(); int len=queue.size(); if(a.left!=null) queue.offer(a.left); if(a.right!=null) queue.offer(a.right); while(len>0){ Node b=queue.poll(); if(b.left!=null) queue.offer(b.left); if(b.right!=null) queue.offer(b.right); a.next=b; a=a.next; len--; } } } }
题解区中一个非常优秀的递归做法：
class Solution { Map<Integer, Node> map = new HashMap<>(); public Node connect(Node root) { helper(root, 0); return root; } void helper(Node node, int deepth){ if(node == null) return; if(map.containsKey(deepth)){ map.get(deepth).next = node; } map.put(deepth, node); helper(node.left, deepth + 1); helper(node.right, deepth + 1); } }
👊9.二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
题目链接：二叉树的最大深度https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
这道题其实用深度优先搜索的递归做法是最简单的。但利用广搜的层序遍历同样非常容易理解。 while(!queue.isEmpty())循环每次进入一次都代表着会进入新的一层去遍历，我们只需要去统计进入了多少次第一个whille循环即可。
层序遍历模板做法：
class Solution { int ans=0; public int maxDepth(TreeNode root) { bfs(root); return ans; } void bfs(TreeNode root){ if(root==null) return; Queue<TreeNode> queue=new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()){ int len=queue.size(); ans++; while(len-->0){ TreeNode x=queue.poll(); if(x.left!=null) queue.offer(x.left); if(x.right!=null) queue.offer(x.right); } } } }
深搜的递归做法：
class Solution { public int maxDepth(TreeNode root) { if(root==null) return 0; return Math.max(maxDepth(root.left),maxDepth(root.right))+1; } }
👊10.二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
题目链接：二叉树的最小深度https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
这道题同上，利用深度优先搜索的递归做法是最简单的。但同样我们这里利用层序遍历去做，如果能知道一个结点是叶子结点呢？当然是它没有左子节点和右子结点的时候，我们同样每次像上一题一样去记录进入循环的次数，当判断到某个结点是子结点，说明该结点所在层的深度就是最小深度
class Solution { int min=Integer.MAX_VALUE; public int minDepth(TreeNode root) { bfs(root); return min==Integer.MAX_VALUE?0:min; } void bfs(TreeNode root){ if(root==null) return; Queue<TreeNode> queue=new LinkedList<>(); queue.offer(root); int ans=0; while(!queue.isEmpty()){ int len=queue.size(); ans++; while(len-->0){ TreeNode x=queue.poll(); if(x.left==null&&x.right==null) min=Math.min(ans,min); if(x.left!=null) queue.offer(x.left); if(x.right!=null) queue.offer(x.right); } } } }
深度优先搜索的递归做法
class Solution { public int minDepth(TreeNode root) { if(root==null) return 0; if(root.left==null&&root.right==null) return 1; if(root.left==null) return minDepth(root.right)+1; if(root.right==null) return minDepth(root.left)+1; return Math.min(minDepth(root.left),minDepth(root.right))+1; } }
🍓3.胜利感谢
可以发现这十道题用上层序遍历后，大部分题只需要在一个模板代码进行稍微地改动即可AC。由此可见层序遍历之强大，是我们必须要掌握的技能之一。同时建议大家一定要自己每次重新手敲而不要去复制粘贴，以加深自己的印象和理解能力。当然每道题的做法也很多，大家也应该去学习一下更加优秀的做法。
