每日一道 LeetCode (23)：二叉樹的層次遍歷 II
?每天 3 分鐘，走上算法的逆襲之路。
?
前文合集
代碼倉庫
GitHub：https://github.com/meteor1993/LeetCode
Gitee：https://gitee.com/inwsy/LeetCode
題目：二叉樹的層次遍歷 II
題目來源：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
給定一個二叉樹，返回其節(jié)點值自底向上的層次遍歷。（即按從葉子節(jié)點所在層到根節(jié)點所在的層，逐層從左向右遍歷）
例如：給定二叉樹 [3,9,20,null,null,15,7],
????3
???/?\
??9??20
????/??\
???15???7
返回其自底向上的層次遍歷為：
[
??[15,7],
??[9,20],
??[3]
]
解題思路
看到這道題，如果還有不會做的同學(xué)，可能需要受到馬桶搋子的教育。
這道題和昨天的那道題基本上是同一道題，昨天的那道題是一個順序遍歷，這道題是一個逆序遍歷。
順序遍歷使用的是隊列的結(jié)構(gòu)，逆序遍歷能想到啥？
當(dāng)然是棧啊，隊列是先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，而棧是一個先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)。
在使用棧的時候只要按照循序把元素一個一個放進(jìn)去放好，最后再拿出來直接就是一個逆序的結(jié)構(gòu)，完全不需要多余的處理的好么。
解法一：使用棧
這個解法就是把昨天的代碼上加上一個棧，在每次循環(huán)的時候把元素放到棧里，最后迭代一次棧，將棧中的元素輸出后返回。
//?順序思維操作?耗時?2ms
public?List>?levelOrderBottom(TreeNode?root)?{
????if?(root?==?null)?return?new?ArrayList<>();
????List>?result?=?new?ArrayList<>();
????Queue?queue?=?new?LinkedList<>();
????queue.offer(root);
????//?新增一個數(shù)據(jù)結(jié)構(gòu)，棧
????Stack>?stack?=?new?Stack<>();
????//?外層循環(huán)，每次循環(huán)都是一層
????while?(!queue.isEmpty())?{
????????int?size?=?queue.size();
????????List?list?=?new?ArrayList<>();
????????//?循環(huán)這一層的所有節(jié)點
????????while?(size?>?0)?{
????????????TreeNode?node?=?queue.poll();
????????????//?將這一層的所有節(jié)點放到?list?中
????????????list.add(node.val);
????????????if?(node.left?!=?null)?queue.offer(node.left);
????????????if?(node.right?!=?null)?queue.offer(node.right);
????????????size--;
????????}
????????//?將列表當(dāng)?shù)罈Ｖ?/span>
????????stack.push(list);
????}
????//?將棧中數(shù)據(jù)取出來放到列表中
????while?(!stack.isEmpty())?{
????????result.add(stack.pop());
????}
????return?result;
}
這段代碼稍微有點長，不過很好理解，完全的順序思維。
不知道你們發(fā)現(xiàn)沒有，越長的代碼越容易看懂，越短的代碼理解起來越費勁，就比如昨天的那個遞歸的方法，總共就兩行，想看懂還是有點難度的。
解法二：使用 List 代替棧
上面的解法耗時稍微有點長，我們需要先把數(shù)據(jù)賽到棧里，然后再迭代整個棧把元素逆序輸出，那么能不能優(yōu)化一下呢？
當(dāng)然可以，我們可以不適用棧，直接使用列表的 List.add(int index,E element) 這個方法，這個方法不懂的建議直接度娘。
//?優(yōu)化代碼，不適用棧，直接使用?list.add?方法，耗時?1ms
public?List>?levelOrderBottom_1(TreeNode?root)?{
????List>?result?=?new?LinkedList<>();
????if?(root?==?null)?return?result;
????Queue?queue?=?new?LinkedList<>();
????queue.offer(root);
????while?(!queue.isEmpty())?{
????????int?size?=?queue.size();
????????List?list?=?new?ArrayList<>();
????????while?(size?>?0)?{
????????????TreeNode?node?=?queue.poll();
????????????list.add(node.val);
????????????if?(node.left?!=?null)?queue.offer(node.left);
????????????if?(node.right?!=?null)?queue.offer(node.right);
????????????size--;
????????}
????????result.add(0,?list);
????}
????return?result;
}
這段代碼沒有加注釋，和上面那段基本一樣，只是單純的去掉了棧，在循環(huán)中使用 result.add(0, list); 將元素放入列表中，從而實現(xiàn)逆序列表的輸出。
