Leetcode|二叉树非递归版后序遍历

二叉树的非递归版后序遍历，首先定义TreeNode如下：

"""

TreeNode class

"""

class TreeNode(object):

    #constructor

    def __init__(self, val):

        self.val = val

        self.right = None

        self.left = None

    val = 0

    right = None

    left = None

非递归后序遍历思路：

cur指针指向当前正遍历到的节点，如果，

满足情况1：不为None，且左孩子不为None，则沿着左侧一直遍历，直到不满足条件；

如不满足情况1，说明要么cur为None,或者左孩子为None，不管哪种情况，都先拿出stack中的最后一个元素，又细分为两种情况：

1. cur的右孩子不为None，且未访问过，则伸向cur的右子树遍历

2. 若不满足（要么cur没有右孩子，要么右孩子访问过），不论哪种情况，都要访问cur节点了，访问后出栈，标记它为访问过，同时当前访问的元素置为None。

---

python代码实现如下：

"""

post order using stack for binary tree

"""

def postOrderUsingStack(node=None):

    visits=[]

    stack = []

    if node is None:

        return

    stack.append(node)

    cur = node

    visited=None

    while len(stack)>0:

        if cur is not None and cur.left is not None:

            stack.append(cur.left)

            cur = cur.left

        else:

            cur =stack[-1]

            # right child for current node is not None and is not visited

            if cur.right is not None and cur.right!=visited:

                cur=cur.right

                stack.append(cur)

            else:

                # do a visit

                visits.append(cur.val)

                stack.pop()

                visited = cur

                cur=None

    return visits

---

单测试如下：

root = TreeNode(1)

root.left=TreeNode(2)

root.left.left = TreeNode(4)

root.right = TreeNode(3)

vals = postOrderUsingStack(root)

print(vals)

后序遍历的结果如下：