Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes' values.

For example:

Given binary tree {1,#,2,3},

1    \     2    /   3

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

'''Created on Nov 18, 2014@author: ScottGu
         
          '''# Definition for a  binary tree node# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution:    # @param root, a tree node    # @return a list of integers    def preorderTraversal(self, root):        stack=[]        vals=[]        if(root==None): return vals        node=root        stack.append(node)        while(len(stack)!=0):            node=stack.pop()            if(node==None): continue            vals.append(node.val)            stack.append(node.right)            stack.append(node.left)                return vals
         

 

Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values.

For example:

Given binary tree {1,#,2,3},

1    \     2    /   3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

confused what "{1,#,2,3}" means? 

'''Created on Nov 18, 2014@author: ScottGu
            
             '''# Definition for a  binary tree node# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution:    # @param root, a tree node    # @return a list of integers    def inorderTraversal(self, root):        stack=[]        vals=[]        visited={}        if(root==None): return vals        node=root        stack.append(node)        visited[node]=1        while(len(stack)!=0):            if(node.left!=None and visited.has_key(node.left)==False):                node=node.left                 stack.append(node)                visited[node]=1            else:                node=stack.pop()                if(node==None): continue                vals.append(node.val)                if(node.right!=None):                    stack.append(node.right)                    node=node.right        return vals
            

 

Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes' values.

For example:

Given binary tree {1,#,2,3},

1    \     2    /   3

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

'''Created on Nov 19, 2014@author: ScottGu
               
                '''# Definition for a  binary tree node# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution:    # @param root, a tree node    # @return a list of integers    def postorderTraversal(self, root):        visited={}        stack=[]        vals=[]        if(root==None): return vals        node=root                stack.append(node)        visited[node]=1                while(len(stack)!=0):            node=stack[-1]            if(node.left !=None and visited.has_key(node.left)==False):                stack.append(node.left)                visited[node.left]=1                continue            else:                      if(node.right!=None and visited.has_key(node.right)==False):                    stack.append(node.right)                    visited[node.right]=1                    continue            node=stack.pop()            if(node==None): continue            vals.append(node.val)        return vals