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 result def traverse(self,root,result): if root is None: return result.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
144. Binary Tree Preorder Traversal
原文：http://www.cnblogs.com/bubbleStar/p/6357630.html