题目描述：

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].

题目大意：

给定一棵二叉树，返回节点值的先序遍历结果（尽量使用非递归算法）。

解题思路：

使用数据结构栈（Stack）

先序遍历非递归算法的伪代码如下（摘自Wikipedia）：

iterativePreorder(node)
  parentStack = empty stack
  while (not parentStack.isEmpty() or node ≠ null)
    if (node ≠ null) 
      visit(node)
      if (node.right ≠ null) parentStack.push(node.right) 
      node = node.left   
    else     
      node = parentStack.pop()

Python代码：

# 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 preorderTraversal(self, root):
        ans = []
        top = root
        stack = []
        while top or stack:
            if top is None:
                top = stack.pop()
            ans.append(top.val)
            if top.right:
                stack.append(top.right)
            top = top.left
        return ans

 

本文链接：http://bookshadow.com/weblog/2015/01/28/leetcode-binary-tree-preorder-traversal/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码