題目
給定一個(gè)二叉樹蛙粘，返回其節(jié)點(diǎn)值自底向上的層次遍歷随闽。 （即按從葉子節(jié)點(diǎn)所在層到根節(jié)點(diǎn)所在的層父丰，逐層從左向右遍歷）
例如：
給定二叉樹 [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回其自底向上的層次遍歷為：
[
[15,7],
[9,20],
[3]
]
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)掘宪，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處蛾扇。
解題思路
使用stack保存每一層節(jié)點(diǎn)攘烛，遍歷取值同時(shí)保存下一層的節(jié)點(diǎn)。
- 因?yàn)橐嫦蜉敵銎ㄉ＃砸孓D(zhuǎn)序列医寿。
代碼
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def levelOrderBottom(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if not root:
return []
res = []
stack = [root]
while stack:
nodes = []
temp = []
for node in stack:
nodes.append(node.val)
if node.left:
temp.append(node.left)
if node.right:
temp.append(node.right)
stack = temp
res.append(nodes)
return res[::-1]
