题解 | 求二叉树的前序遍历

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

#
# 
# @param root TreeNode类 
# @return int整型一维数组
#
class Solution:
    def preorderTraversal(self , root ):
        # write code here
        # 
        # **************递归法************
        # p = []
        # def dfs(r):
        #     if r == None :
        #         return []
        #     p.append(r.val)
        #     dfs(r.left)
        #     dfs(r.right)
        # dfs(root)
        # return p
        # **************递归法************

        # **************迭代法************
        def inorder_traversal(root):
            stack = []
            output = []
            p = root
            if not p:
                return output
            while len(stack) > 0 or p is not None:
                while p:
                    stack.append(p)
                    output.append(p.val)
                    p = p.left                 
                p = stack.pop()
                p = p.right
                # if p.right != None:
                #     stack.append(p.right)
            return output
        return inorder_traversal(root)
        # **************迭代法************