首页 > 代码库 > [leetcode]Binary Tree Preorder Traversal @ Python

[leetcode]Binary Tree Preorder Traversal @ Python

原题地址:http://oj.leetcode.com/problems/binary-tree-preorder-traversal/

题意:这题用递归比较简单。应该考察的是使用非递归实现二叉树的先序遍历。先序遍历的遍历顺序是:根,左子树,右子树。

解题思路:如果树为下图:

                      1

                     /     \

                    2         3

                   /     \    /    \

                   4       5  6     7 

    使用一个栈。步骤为:

    一,先遍历节点1,并入栈,如果有左孩子,继续遍历并入栈,一直到栈为{1,2,4}。

    二,开始弹栈,当栈顶元素为2时,弹出2,并检测2存在右孩子5,于是遍历5并入栈,此时栈为{1,5}。

    三,弹出5,5没有左右孩子,继续弹栈,将1弹出后,栈为{}。

    四,由于1存在右孩子,则继续按照以上步骤入栈出栈。{3, 6}->{7}->{},结束。

    栈的状态变化:{1}->{1,2}->{1,2,4}->{1,2}->{1}->{1,5}->{1}->{}->{3}->{3,6}->{3}->{}->{7}->{}。

代码:

# 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 iterative_preorder(self, root, list):
        stack = []
        while root or stack:
            if root:
                list.append(root.val)
                stack.append(root)
                root = root.left
            else:
                root = stack.pop()
                root = root.right
        return list
    
    def recursive_preorder(self, root, list):
        if root:
            list.append(root.val)
            self.preorder(root.left,list)
            self.preorder(root.right,list)

    def preorderTraversal(self,root):
        list = []
        self.iterative_preorder(root,list)
        return list