144. Binary Tree Preorder Traversal

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

?該題是對樹做前序遍歷

下面分別是遞歸，非遞歸，分治三種思路的解題結果

#遞歸寫法
class Solution(object):def preorderTraversal(self, root):""":type root: TreeNode:rtype: List[int]"""if root is None:return []result = []self.traverse(root,result)return resultdef traverse(self,root,result):if root is None:returnresult.append(root.val)self.traverse(root.left,result)self.traverse(root.right,result)   

#分治法
class Solution(object):def preorderTraversal(self, root):""":type root: TreeNode:rtype: List[int]"""if root is None:return []result = []#分left = self.preorderTraversal(root.left)right = self.preorderTraversal(root.right)#治result.append(root.val)result.extend(left)result.extend(right)return result

#非遞歸寫法，用棧模擬
class Solution(object):def preorderTraversal(self, root):""":type root: TreeNode:rtype: List[int]"""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   

?