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