LeetCode----Binary Tree Postorder Traversal

来源:互联网 时间:1970-01-01

Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes' values.

For example:

Given binary tree

{1,#,2,3}
,

1 / 2 / 3


return
[3,2,1]
.

Note: Recursive solution is trivial, could you do it iteratively?

分析:

非递归后序遍历二叉树。后序遍历遍历需要注意的是在面对一个节点时,如何确定其左右节点是否都被访问了,只有左右节点都被访问了才可以访问当前节点,否则按照先左后右的顺序来访问。在Python中,完全可以存储每个节点的访问情况来进行遍历,只是需要更多地存储空间。

这里还是用一个栈和一个记录的访问指针来完成。

代码:

# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution(object): def postorderTraversal(self, root):""":type root: TreeNode:rtype: List[int]"""pre = Nonest = []res = []p = rootwhile p or st: while p:st.append(p)p = p.left p = st[-1] if p.right is None or p.right == pre:res.append(p.val)pre = pst.pop()p = None else:p = p.rightreturn res



相关阅读:
Top