https://leetcode-cn.com/problems/binary-tree-postorder-traversal/submissions/
感觉后序遍历是最难实现的,左右根的顺序,用非递归比较难搞。所以换了一个思路,写了根右左,最后对结果输出进行逆序就是左右根了。
下面的代码用stack实现的时候,根进去了,需要先进去左,再进去右,这样pop出来的才会先是右,才是左。相当于又进行了一个逆向思维。
class Solution(object):
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if not root:
return []
arr = []
nodes = [root]
while nodes:
tmp = nodes.pop()
arr.append(tmp.val)
if tmp.left: # 注意一定是先左再右
nodes.append(tmp.left)
if tmp.right:
nodes.append(tmp.right)
return arr[::-1]
网友评论