>

自由软件精神——“自由、开放、分享”。自由软件自诞生之日起,就秉承了学术自由的思想,信奉科学无国界,知识应该全人类共享。

ubuntu精神——人道待人,天下共享连接人人的信念。具有 ubuntu 精神的人心胸开阔,乐于助人,见贤思齐而不忌妒贤能......

二叉树的前序中序后序遍历的非递归实现

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param root, a tree node
    # @return a list of integers
    def postorderTraversal(self, root):
        if root is None: return []
        stack=[]
        ans=[]
        self.push_right(stack,root,ans)
        while len(stack):
            node=stack[-1]
            stack.pop()
            self.push_right(stack,node.left,ans)
        return ans[::-1]
        
    def push_right(self,stack,root,ans):
        while root:
            stack.append(root)
            ans.append(root.val)
            root=root.right

 

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param root, a tree node
    # @return a list of integers
    def inorderTraversal(self, root):
        if root is None: return []
        stack=[]
        ans=[]
        self.push_left(stack,root)
        while len(stack):
            node=stack[-1]
            ans.append(node.val)
            stack.pop()
            self.push_left(stack,node.right)
        return ans
        
    def push_left(self,stack,root):
        while root:
            stack.append(root)
            root=root.left

 

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param root, a tree node
    # @return a list of integers
    def preorderTraversal(self, root):
        if root is None: return []
        stack=[]
        ans=[]
        self.push_left(stack,root,ans)
        while len(stack):
            node=stack[-1]
            stack.pop()
            self.push_left(stack,node.right,ans)
        return ans
        
    def push_left(self,stack,root,ans):
        while root:
            stack.append(root)
            ans.append(root.val)
            root=root.left

Meta

发布: 十二月 15, 2014

作者: Bone Lee 李智华

评论:  

字数统计: 248

下一篇: tornado gen_test含义

上一篇: mongodb聚合

Bookmark and Share

Tags

python

comments powered by Disqus

返回顶部