美文网首页
后序遍历--非递归

后序遍历--非递归

作者: hustyanye | 来源:发表于2019-07-16 23:00 被阅读0次

https://leetcode-cn.com/problems/binary-tree-postorder-traversal/submissions/

感觉后序遍历是最难实现的,左右根的顺序,用非递归比较难搞。所以换了一个思路,写了根右左,最后对结果输出进行逆序就是左右根了。
下面的代码用stack实现的时候,根进去了,需要先进去左,再进去右,这样pop出来的才会先是右,才是左。相当于又进行了一个逆向思维。

class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        arr = []
        nodes = [root]
        while nodes:
            tmp = nodes.pop()
            arr.append(tmp.val)
            if tmp.left: # 注意一定是先左再右
                nodes.append(tmp.left)
            if tmp.right:
                nodes.append(tmp.right)
            
        return arr[::-1]

相关文章

  • 二叉树遍历

    先序遍历——[递归、非递归] 中序遍历——[递归、非递归] 后序遍历——[递归、非递归] 层次遍历——[递归、非递归]

  • 二叉树的遍历

    非递归前序遍历 非递归中序遍历 非递归后序遍历 层序遍历

  • 树的遍历,golang实现

    先序,递归 中序,递归 后序,递归 先序,非递归 中序,非递归 后序,非递归 层序遍历

  • 二叉树的前中后三种遍历(递归、非递归和Morris)

    前序遍历 递归版本 非递归版本 中序遍历 递归版本 非递归版本 Morris 遍历待补充 后序遍历 递归版本 非递...

  • 二叉树的遍历算法

    递归版本 先序遍历: 中序遍历: 后序遍历: 非递归版本 先序遍历: 中序遍历: 后序遍历: 层次遍历:

  • 树的遍历

    节点结构: 先序遍历 递归 非递归 后序遍历 递归 非递归 中序遍历 递归 非递归 层序遍历 类库 有了上述遍历算...

  • 二叉树前、中、后序遍历、层次遍历

    1、前序遍历 非递归:利用Stack实现 递归 2、中序遍历 非递归:利用Stack实现 递归: 3、后序遍历 非...

  • 二叉树的遍历

    先序递归: 非递归: 中序递归: 非递归: 后序递归: 非递归 层次遍历

  • Leetcode-145题:Binary Tree Postor

    题目 非递归后序遍历 代码

  • 数据结构-树的遍历

    1. 先序遍历 递归实现 非递归实现 2. 中序遍历 递归实现 非递归实现 3. 后序遍历 递归实现 非递归实现 ...

网友评论

      本文标题:后序遍历--非递归

      本文链接:https://www.haomeiwen.com/subject/bvgxlctx.html