定制网站建设功能报价表模板,群晖wordpress主机,旅游小程序哪家做得好,快设计网站官网leetcode 145. Binary Tree Postorder Traversal 思路一#xff1a; 使用一个栈stack保存经过的根结点#xff0c;另一个栈flag保存每个结点的右子树是否遍历#xff1b;如果根结点存在#xff0c;结点入栈#xff0c;并把结点的右子树遍历结果置为0#xff0c;代表没遍历… leetcode 145. Binary Tree Postorder Traversal 思路一 使用一个栈stack保存经过的根结点另一个栈flag保存每个结点的右子树是否遍历如果根结点存在结点入栈并把结点的右子树遍历结果置为0代表没遍历把root指向左子树如果栈不为空判断栈顶元素右子树是否存在以及是否已经遍历如果存在并且没有遍历则把root指向右子树否则结点出栈并且把结点的右子树遍历标志出栈重复2-4直到栈空或者root不存在。这是第一个一下想到的思路可以看到用了两个栈作为额外的空间复杂度不是很好并且在leetcode上提交后运行时间感觉也不甚理想有没有更好的方法呢# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val x
# self.left None
# self.right Noneclass Solution(object):def postorderTraversal(self, root)::type root: TreeNode:rtype: List[int]ret []stack []flag []while root or stack:while root:stack.append(root)flag.append(0)root root.leftif stack:top stack[-1]if top.right and not flag[-1]:flag[-1] 1root top.rightelse:flag.pop()ret.append(stack.pop().val)return ret 感觉在学校时接触的第一门语言是C数据结构也是基于C学的导致第一印象总是往上面靠写出来的代码不是很Pythonic下面是一个我觉得更好的代码更少也更容易理解的方法。思路二 后续遍历根结点先遍历左子树然后遍历右子树此时反过来考虑先遍历根结点然后遍历右子树最后是左子树这样就可以转化为和先序遍历一个类型了最后只把遍历结果逆序输出就ok了而先序遍历是之前写过并且比较好理解的。 使用栈存储结点当结点存在或者栈不为空判断结点当结点存在结点值保存结点入栈并将指针指向结点的右子树当栈不为空结点出栈并将指针指向左子树重复2-4直到结果产生逆序输出结果利用Python列表的-1.# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val x
# self.left None
# self.right Noneclass Solution(object):def postorderTraversal(self, root)::type root: TreeNode:rtype: List[int]ret []stack []while root or stack:while root:ret.append(root.val)stack.append(root)root root.rightif stack:top stack.pop()root top.leftreturn ret[::-1] 转载于:https://www.cnblogs.com/qiaojushuang/p/7887517.html
