資訊專欄INFORMATION COLUMN
摘要：題目給定一個(gè)二叉樹，返回其按層次遍歷的節(jié)點(diǎn)值。例如給定二叉樹返回其層次遍歷結(jié)果題解我們數(shù)據(jù)結(jié)構(gòu)的書上教的層序遍歷就是利用一個(gè)隊(duì)列不斷的把左子樹和右子樹入隊(duì)。
題目
給定一個(gè)二叉樹，返回其按層次遍歷的節(jié)點(diǎn)值。 （即逐層地，從左到右訪問所有節(jié)點(diǎn)）。
例如:
給定二叉樹: [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回其層次遍歷結(jié)果：
[ [3], [9,20], [15,7] ]題解
我們數(shù)據(jù)結(jié)構(gòu)的書上教的層序遍歷,就是利用一個(gè)隊(duì)列,不斷的把左子樹和右子樹入隊(duì)。但是這個(gè)題目還要要求按照層輸出。所以關(guān)鍵的問題是： 如何確定是在同一層的。
我們很自然的想到：
如果在入隊(duì)之前,把上一層所有的節(jié)點(diǎn)出隊(duì),那么出隊(duì)的這些節(jié)點(diǎn)就是上一層的列表。
由于隊(duì)列是先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu),所以這個(gè)列表是從左到右的。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List> levelOrder(TreeNode root) {
List> res = new LinkedList<>();
if (root == null) {
return res;
}
LinkedList queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
List currentRes = new LinkedList<>();
// 當(dāng)前隊(duì)列的大小就是上一層的節(jié)點(diǎn)個(gè)數(shù), 依次出隊(duì)
while (size > 0) {
TreeNode current = queue.poll();
if (current == null) {
continue;
}
currentRes.add(current.val);
// 左子樹和右子樹入隊(duì).
if (current.left != null) {
queue.add(current.left);
}
if (current.right != null) {
queue.add(current.right);
}
size--;
}
res.add(currentRes);
}
return res;
}
}
這道題可不可以用非遞歸來解呢?
遞歸的子問題：遍歷當(dāng)前節(jié)點(diǎn), 對于當(dāng)前層, 遍歷左子樹的下一層層,遍歷右子樹的下一層
遞歸結(jié)束條件: 當(dāng)前層,當(dāng)前子樹節(jié)點(diǎn)是null
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List> levelOrder(TreeNode root) {
List> res = new LinkedList<>();
if (root == null) {
return res;
}
levelOrderHelper(res, root, 0);
return res;
}
/**
* @param depth 二叉樹的深度
*/
private void levelOrderHelper(List> res, TreeNode root, int depth) {
if (root == null) {
return;
}
if (res.size() <= depth) {
// 當(dāng)前層的第一個(gè)節(jié)點(diǎn),需要new 一個(gè)list來存當(dāng)前層.
res.add(new LinkedList<>());
}
// depth 層,把當(dāng)前節(jié)點(diǎn)加入
res.get(depth).add(root.val);
// 遞歸的遍歷下一層.
levelOrderHelper(res, root.left, depth + 1);
levelOrderHelper(res, root.right, depth + 1);
}
}
熱門閱讀
技術(shù)文章匯總
【Leetcode】101. 對稱二叉樹
【Leetcode】100. 相同的樹
【Leetcode】98. 驗(yàn)證二叉搜索樹
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/73439.html
102. 二叉樹的層次遍歷 題目描述 給定一個(gè)二叉樹，返回其按層次遍歷的節(jié)點(diǎn)值。 （即zhucengde，從左到右訪問）。 例如: 給定二叉樹: [3,9,20,null,null,15,7], 3 / 9 20 / 15 7 返回其層次遍歷結(jié)果為： [ [3], [9,20], [15,7] ] class Solution: def le...
摘要：題目給定一個(gè)二叉樹，返回其節(jié)點(diǎn)值的鋸齒形層次遍歷。例如給定二叉樹返回鋸齒形層次遍歷如下題解這道題要求用字型就是要求知道深度。稍作改動(dòng)的是需要在遍歷左子樹和右子樹的時(shí)候帶上深度的信息，才能知道是加在列表頭還是列表尾部。 題目 給定一個(gè)二叉樹，返回其節(jié)點(diǎn)值的鋸齒形層次遍歷。（即先從左往右，再從右往左進(jìn)行下一層遍歷，以此類推，層與層之間交替進(jìn)行）。 例如：給定二叉樹 [3,9,20,null...
摘要：在線網(wǎng)站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...
摘要：小鹿題目二叉樹中序遍歷給定一個(gè)二叉樹，返回它的中序遍歷。通常遞歸的方法解決二叉樹的遍歷最方便不過，但是我還是喜歡增加點(diǎn)難度，用一般的迭代循環(huán)來實(shí)現(xiàn)。 Time：2019/4/25Title:Binary Tree Inorder TraversalDifficulty: MediumAuthor:小鹿 題目：Binary Tree Inorder Traversal（二叉樹中序遍歷...
閱讀 2513·2023-04-25 17:27
閱讀 1824·2019-08-30 15:54
閱讀 2369·2019-08-30 13:06
閱讀 2980·2019-08-30 11:04
閱讀 746·2019-08-29 15:30
閱讀 729·2019-08-29 15:16
閱讀 1733·2019-08-26 10:10
閱讀 3603·2019-08-23 17:02
