【算法系列-二叉樹】層序遍歷

1. 算法分析🛸

二叉樹的層序遍歷就是對(duì)樹進(jìn)行廣度優(yōu)先搜索，一層一層的對(duì)樹的節(jié)點(diǎn)進(jìn)行遍歷；

【題目鏈接】102. 二叉樹的層序遍歷 - 力扣（LeetCode）

在這里，我們通過隊(duì)列來輔助實(shí)現(xiàn)二叉樹的層序遍歷，關(guān)鍵在于尋找到判斷當(dāng)前節(jié)點(diǎn)正在哪一層且這一層的節(jié)點(diǎn)是否遍歷完的條件。

解題過程🎬

定義一個(gè)size，這個(gè)size等于當(dāng)前隊(duì)列的長(zhǎng)度大小；

開始先將根節(jié)點(diǎn)加入隊(duì)列，形成第一層； 此時(shí)size = 1，再將隊(duì)列中的節(jié)點(diǎn)彈出，將該節(jié)點(diǎn)的左右節(jié)點(diǎn)加入隊(duì)列(非空)，同時(shí)size - 1；

重復(fù)上述過程，直到size = 0時(shí)，表示當(dāng)前層數(shù)的節(jié)點(diǎn)已經(jīng)遍歷完，進(jìn)入下一層，直到隊(duì)列為空，返回結(jié)果

代碼示例🌰

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> ret = new ArrayList<>();if (root == null) {return ret;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {List<Integer> list = new ArrayList<>();int size = queue.size();while (size > 0) {TreeNode cur = queue.poll();list.add(cur.val);if (cur.left != null) {queue.offer(cur.left);}if (cur.right != null) {queue.offer(cur.right);}size--;}ret.add(list);}return ret;}
}

下面提供一些與層序遍歷解法相似的類型題:

2. 相似題型🎯

2.1 二叉樹的層序遍歷II(LeetCode 107)

【題目鏈接】107. 二叉樹的層序遍歷 II - 力扣（LeetCode）

代碼示例🌰

class Solution {public List<List<Integer>> levelOrderBottom(TreeNode root) {List<List<Integer>> ret = new ArrayList<>();if (root == null) {return ret;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {List<Integer> list = new ArrayList<>();int size = queue.size();while (size > 0) {TreeNode cur = queue.poll();list.add(cur.val);if (cur.left != null) {queue.offer(cur.left);}if (cur.right != null) {queue.offer(cur.right);}size--;}ret.add(0, list);}return ret;}
}

2.2 二叉樹的右視圖(LeetCode 199)

【題目鏈接】199. 二叉樹的右視圖 - 力扣（LeetCode）

解題思路與使用隊(duì)列的層序遍歷相同，需要注意的是要找到能夠在右視圖看到的節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)可以是左節(jié)點(diǎn)也可以是右節(jié)點(diǎn)，但它一定是每一層遍歷的最右邊節(jié)點(diǎn)，對(duì)此在遍歷到隊(duì)列中size為0的前一個(gè)節(jié)點(diǎn)時(shí)，將這個(gè)節(jié)點(diǎn)的值加入返回?cái)?shù)組即可

代碼示例🌰

class Solution {public List<Integer> rightSideView(TreeNode root) {List<Integer> ret = new ArrayList<>();if (root == null) {return ret;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int size = queue.size();while (size > 1) {queueOfferNode(queue);size--;}TreeNode node = queueOfferNode(queue);ret.add(node.val);}return ret;}TreeNode queueOfferNode(Queue<TreeNode> queue) {TreeNode cur = queue.poll();if (cur.left != null) {queue.offer(cur.left);}if (cur.right != null) {queue.offer(cur.right);}return cur;}
}

2.3 二叉樹的層平均值(LeetCode 637)

【題目鏈接】637. 二叉樹的層平均值 - 力扣（LeetCode）

代碼示例🌰

class Solution {public List<Double> averageOfLevels(TreeNode root) {List<Double> ret = new ArrayList<>();if (root == null) {return ret;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int size = queue.size();int num = size;double sum = 0;while (size > 0) {TreeNode cur = queue.poll();sum += cur.val;if (cur.left != null) {queue.offer(cur.left);}if (cur.right != null) {queue.offer(cur.right);}size--;}ret.add(sum / num);}return ret;}
}

2.4 N叉樹的層序遍歷(LeetCode 429)

【題目鏈接】429. N 叉樹的層序遍歷 - 力扣（LeetCode）

代碼示例🌰

/*
// Definition for a Node.
class Node {public int val;public List<Node> children;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, List<Node> _children) {val = _val;children = _children;}
};
*/class Solution {public List<List<Integer>> levelOrder(Node root) {List<List<Integer>> ret = new ArrayList<>();if (root == null) {return ret;}Queue<Node> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {List<Integer> list = new ArrayList<>();int size = queue.size();while (size > 0) {Node cur = queue.poll();list.add(cur.val);List<Node> children = cur.children;for (Node node : children) {if (node != null) {queue.offer(node);}}size--;}ret.add(list);}return ret;}
}

2.5 在每個(gè)樹行中找最大值(LeetCode 515)

【題目鏈接】515. 在每個(gè)樹行中找最大值 - 力扣（LeetCode）

代碼示例🌰

class Solution {public List<Integer> largestValues(TreeNode root) {List<Integer> ret = new ArrayList<>();if (root == null) {return ret;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int size = queue.size();int max = Integer.MIN_VALUE;while (size > 0) {TreeNode cur = queue.poll();if (cur.val > max) {max = cur.val;}if (cur.left != null) {queue.offer(cur.left);}if (cur.right != null) {queue.offer(cur.right);}size--;}ret.add(max);}return ret;}
}

2.6 填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)節(jié)點(diǎn)指針(LeetCode 116)

【題目鏈接】116. 填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)節(jié)點(diǎn)指針 - 力扣（LeetCode）

代碼示例🌰

/*
// Definition for a Node.
class Node {public int val;public Node left;public Node right;public Node next;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, Node _left, Node _right, Node _next) {val = _val;left = _left;right = _right;next = _next;}
};
*/class Solution {public Node connect(Node root) {if (root == null) {return root;}Queue<Node> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int size = queue.size();while (size-- > 0) {Node cur1 = queue.poll();Node cur2 = size == 0 ? null : queue.peek();cur1.next = cur2;if (cur1.left != null) {queue.offer(cur1.left);}if (cur1.right != null) {queue.offer(cur1.right);}}}return root;}
}

2.7 二叉樹的最大深度(LeetCode 104)

【題目鏈接】104. 二叉樹的最大深度 - 力扣（LeetCode）

代碼示例🌰

class Solution {public int maxDepth(TreeNode root) {int ret = 0;if (root == null) {return ret;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {ret++;int size = queue.size();while (size > 0) {TreeNode cur = queue.poll();if (cur.left != null) {queue.offer(cur.left);}if (cur.right != null) {queue.offer(cur.right);}size--;}}return ret;}
}

2.8 二叉樹的最小深度(LeetCode 111)

【題目鏈接】111. 二叉樹的最小深度 - 力扣（LeetCode）

代碼示例🌰

class Solution {public int minDepth(TreeNode root) {int ret = 0;if (root == null) {return ret;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {ret++;int size = queue.size();while (size > 0) {TreeNode cur = queue.poll();if (cur.left == null && cur.right == null) {return ret;}if (cur.left != null) {queue.offer(cur.left);}if (cur.right != null) {queue.offer(cur.right);}size--;}}return ret;}
}

以上便是對(duì)二叉樹層序遍歷問題的介紹了！！后續(xù)還會(huì)繼續(xù)分享其它算法系列內(nèi)容，如果這些內(nèi)容對(duì)大家有幫助的話請(qǐng)給一個(gè)三連關(guān)注吧💕( ?? ω ?? )?( ?? ω ?? )??