二叉树先序遍历

堆栈实现

def stack_print(root):
    stack = []
    result = []
    while root or stack:
        while root:
            stack.append(root)
            result.append(root.val)
            root = root.left
        if stack:
            root = stack.pop()
            root = root.right
    return result

递归实现

def recursive_print(root):
    result = []
    def preorder(root):
        if not root:
            return
        result.append(root.val)
        preorder(root.left)
        preorder(root.right)
    preorder(root)
    return result

完整代码

class BinTree(object):
    def __init__(self, root):
        self.root = root
    def stack_print(self, root):
        """堆栈实现"""
        stack = []
        while root or stack:
            while root:
                stack.append(root)
                print(root.val)
                root = root.left
            if stack:
                root = stack.pop()
                root = root.right
    def recursive_print(self, root):
        """递归实现"""
        if not root:
            return
        print(root.val)
        self.recursive_print(root.left)
        self.recursive_print(root.right)
def main():
    left = TreeNode(2, left=TreeNode(4), right=TreeNode(5))
    right = TreeNode(3, left=TreeNode(6), right=TreeNode(7))
    root = TreeNode(1, left=left, right=right)
    tree = BinTree(root)
    print('递归 先序遍历:')
    tree.recursive_print(tree.root)
    print('堆栈 先序遍历:')
    tree.stack_print(tree.root)