66. 二叉樹的前序遍歷

給出一棵二叉樹，返回其節(jié)點(diǎn)值的前序遍歷。

樣例

樣例 1:

輸入：{1,2,3}

輸出：[1,2,3]

解釋：

1

/ \

2 3

它將被序列化為{1,2,3}

前序遍歷

樣例 2:

輸入：{1,#,2,3}

輸出：[1,2,3]

解釋：

1

\

2

/

3

它將被序列化為{1,#,2,3}

前序遍歷

挑戰(zhàn)

你能使用非遞歸實(shí)現(xiàn)么？

注意事項(xiàng)

首個(gè)數(shù)據(jù)為根節(jié)點(diǎn)，后面接著是其左兒子和右兒子節(jié)點(diǎn)值，"#"表示不存在該子節(jié)點(diǎn)。

節(jié)點(diǎn)數(shù)量不超過20

前序遍歷，就是先找根節(jié)點(diǎn)的值，再找左兒子節(jié)點(diǎn)的值，等所有左子兒子的值遍歷以后，再遍歷右兒子的子(即遍歷所有的左兒子節(jié)點(diǎn)的值后再遍歷右兒子節(jié)點(diǎn)的值)。

"""

這是使用遞歸法實(shí)現(xiàn)

Definition of TreeNode:

class TreeNode:

def __init__(self, val):

self.val = val

self.left, self.right = None, None

"""

class Solution:

"""

@param root: A Tree

@return: Preorder in ArrayList which contains node values.

"""

def preorderTraversal(self, root):

# write your code here

if root is None:

return []

re = [root.val]

if root.left is not None:

re = re + self.preorderTraversal(root.left)

if root.right is not None:

re = re + self.preorderTraversal(root.right)

return re

在網(wǎng)上找了一下使用非遞歸方法進(jìn)行遍歷，利用了棧的方法進(jìn)行循環(huán)遍歷。之前不太知道棧是什么，看了一下以后，貌似有了了解。

"""

Definition of TreeNode:

class TreeNode:

def __init__(self, val):

this.val = val

this.left, this.right = None, None

"""

class Solution:

"""

@param root: The root of binary tree.

@return: Preorder in list which contains node values.

"""

def preorderTraversal(self, root):

if root is None:

return []

stack = [root]

preorder = []

while stack:

node = stack.pop()

preorder.append(node.val)

if node.right:

stack.append(node.right)

if node.left:

stack.append(node.left)

return preorder

總結(jié)

以上是生活随笔為你收集整理的python非递归前序遍历二叉树_LintCode66：二叉树的前序遍历(python)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。