给定一个二叉树,返回它的 后序 遍历。
进阶: 递归算法很简单,你可以通过迭代算法完成吗?
解法一:递归
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution:def __init__(self):self.ans = []def postorderTraversal(self, root: TreeNode) -> List[int]:if not root:return self.ansself.postorderTraversal(root.left)self.postorderTraversal(root.right)self.ans.append(root.val)return self.ans
后序遍历算法?解法二:迭代
class Solution(object):def postorderTraversal(self, root):""":type root: TreeNode:rtype: List[int]"""if root is None:return []stack = [root, ] # 栈,后进先出output = [] # 存储输出while stack:root = stack.pop()output.append(root.val)if root.left is not None:stack.append(root.left)if root.right is not None:stack.append(root.right)return output[::-1] # 逆序输出
版权声明:本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。
工作时间:8:00-18:00
客服电话
电子邮件
admin@qq.com
扫码二维码
获取最新动态