蛮三刀酱的博客

技术公众号:后端技术漫谈

【Leetcode】【python】Binary Tree Postorder Traversal 二叉树的后序遍历

发表于 更新于 分类于 阅读次数： Valine：

题目大意

二叉树后序遍历
挑战：迭代解题

解题思路

递归简单

代码

###递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    
    def _postorderTraversal(self, root, result):
        if root:
            self._postorderTraversal(root.left, result)
            self._postorderTraversal(root.right, result)
            result.append(root.val)
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if root == None:
            return []
        result = []
        self._postorderTraversal(root, result)
        return result

迭代

将数组输出为右子树-左子树-根节点。最后，再将数组倒序输出，形成后序遍历。这样代码并不用很繁琐，也能做完迭代。（前序遍历是左子树-右子树-根节点）

代码根据前序遍历完美修改：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if root is None:
            return []
        ret = []
        stack = [root]
        while stack:
            node = stack.pop()
            if node:
                ret.append(node.val)
                if node.left:
                    stack.append(node.left)
                if node.right:
                    stack.append(node.right)
        return ret[::-1]

补充思路

1
2
3
4
5
6
7
8
9
	　    1

	　　/　　\

2　　　　3

　　/　\

　　　　　　 4　　5

使用一个栈。分几个步骤：

一，将根节点入栈，并将根节点的孩子入栈，入栈顺序为：先入右孩子，再入左孩子，顺序不能错。因为这样在弹栈时的顺序就是后序遍历的顺序了。如果左孩子还有左孩子或者右孩子，那么继续按先右后左的顺序入栈。那么上面这棵树开始的入栈顺序是：1，3，2。由于2不存在左右孩子，停止入栈。

二，由于2没有左右孩子，遍历2并将2弹出，同时使用prev记录下2这个节点。

三，2出栈后，栈为{1，3}，此时3在栈顶，由于3存在左右孩子，按顺序入栈，此时栈为{1，3，5，4}。

四，将4和5遍历并出栈，此时prev指向5，栈为{1，3}。prev的作用是什么呢？用来判断prev是否为栈顶元素的孩子，如果是，则说明子树的孩子已经遍历完成，需要遍历树根了。以上树为例：4和5出栈后，prev指向5，而5是栈顶元素3的孩子，说明孩子已经遍历完毕，则遍历3然后弹出3即可，即完成了子树{3，4，5}的后序遍历。

五，此时栈为{1}，为树根，而左右子树都遍历完了，最后遍历树根并弹出即可。

总结