python实现leetcode之145. 二叉树的后序遍历

解题思路

不断把离栈顶最近的元素的孩子放入栈中，直到无节点需要处理

145. 二叉树的后序遍历

代码

# 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 postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root: return []
        index, length, stack = 0, 1, [root]
        while index >= 0:
            node = stack[index]
            if node.right:
                stack.append(node.right)
                node.right = None
                index = length
                length += 1
            elif node.left:
                stack.append(node.left)
                node.left = None
                index = length
                length += 1
            else:
                index -= 1
        return [item.val for item in stack[::-1]]
        # def h(tree):
        #     if tree:
        #         h(tree.left)
        #         h(tree.right)
        #         rtv.append(tree.val)
        # h(root)
        # return rtv