[leetcode]Binary Tree Preorder Traversal @ Python

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

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

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

　　　　　　　　　　　　　　　　　　　　　/ \

　　　　　　　　　　　　　　　　　　　　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

巴特西

[leetcode]Binary Tree Preorder Traversal @ Python

最新文章

热门文章