[ LeetCode 145 ] 二叉树的后续遍历

每天分享一个LeetCode题目，从简单到难，每天 5 分钟，一起进步

LeetCode 后续遍历，地址l:https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

树结点类

class TreeNode(object):
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

递归遍历

还是同样的解释，递归遍历通常来说代码形式比较简单和整洁，非常易读。

但是理解起来不是那么容易，然而递归思想对于整个树相关的题目部分是相对比较重要的，因为，递归的思路在很多的题目中很容易就可以进行解决！

好好理解递归，对于很多题目和问题的解决都是很有帮助的

def postorderTraversal(self, root):
    def post_order(root):
        if not root:
            return
        post_order(root.left)
        post_order(root.right)
        res.append(root.val)

    res = []
    post_order(root)
    return res

非递归遍历

二叉树的后续非递归遍历，主要还是用到了栈，这里说一种比较简单的方法

这里用到了两个栈，听起来两个栈会很复杂，其实真的并没有，只要简单的画画图，就会感觉问题神奇的被解决了

1.初始化 2 个栈 s1 和 s2，并且初始化根结点到 s1 中。

2.将 s1 中栈顶元素弹出，在 s2 中压栈，并判断该元素是否有左右孩子，如果有则依次入栈 s1。否则，继续从 s1 中弹出，循环执行。

3.最后将 s2 中元素依次弹出

def postorderTraversal_no_recursion(self, root):
    res = []
    if not root:
        return res
    s1, s2 = [], []
    s1.append(root)
    while s1:
        T = s1.pop()
        s2.append(T)
        if T.left:
            s1.append(T.left)
        if T.right:
            s1.append(T.right)
    while s2:
        res.append(s2.pop().val)
    return res

完整代码

# -*- coding:utf-8 -*-
# !/usr/bin/env python

# 树结点类
class TreeNode(object):
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution(object):
    def postorderTraversal(self, root):
        def post_order(root):
            if not root:
                return
            post_order(root.left)
            post_order(root.right)
            res.append(root.val)

        res = []
        post_order(root)
        return res

    def postorderTraversal_no_recursion(self, root):
        res = []
        if not root:
            return res
        s1, s2 = [], []
        s1.append(root)
        while s1:
            T = s1.pop()
            s2.append(T)
            if T.left:
                s1.append(T.left)
            if T.right:
                s1.append(T.right)
        while s2:
            res.append(s2.pop().val)
        return res


if __name__ == "__main__":
    # 新建节点
    root = TreeNode('A')
    node_B = TreeNode('B')
    node_C = TreeNode('C')
    node_D = TreeNode('D')
    node_E = TreeNode('E')
    node_F = TreeNode('F')
    node_G = TreeNode('G')
    node_H = TreeNode('H')
    node_I = TreeNode('I')
    # 构建二叉树
    #        A
    #      /   \
    #     B     C
    #    / \   / \
    #   D   E F   G
    #  / \
    # H   I
    root.left, root.right = node_B, node_C
    node_B.left, node_B.right = node_D, node_E
    node_C.left, node_C.right = node_F, node_G
    node_D.left, node_D.right = node_H, node_I

    s = Solution()
    print(s.postorderTraversal(root))
    print(s.postorderTraversal_no_recursion(root))