Binary Tree Traverasl with OO and Stack

1、一切都是对象，对象就是关系和操作；每个节点，都有两种操作，print和visit。 2、放在stack里面可以使操作，可以是函数，递归也是面向对象的体现；

Python代码实现如下：

class guide(object): def __init__(self, opt,node): self.opt = opt self.node = node class Solution2(object): def preorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ if root is None: return [] ans = [] path = [guide(0,root),] while path: current = path.pop() if not current.node: continue if current.opt == 1: ans += [current.node.item] else: path += [guide(0,current.node.right)] path += [guide(0,current.node.left)] path += [guide(1,current.node)] return ans def inorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ if root is None: return [] ans = [] path = [guide(0,root),] while path: current = path.pop() if not current.node: continue if current.opt == 1: ans += [current.node.item] else: path += [guide(0,current.node.right)] path += [guide(1,current.node)] path += [guide(0,current.node.left)] return ans def postorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ if root is None: return [] ans = [] path = [guide(0,root),] while path: current = path.pop() if not current.node: continue if current.opt == 1: ans += [current.node.item] else: path += [guide(1,current.node)] path += [guide(0,current.node.right)] path += [guide(0,current.node.left)] return ans

Test case：

if __name__ =="__main__": tree =tree.Node() tree._add(0) tree._add(1) tree._add(2) tree._add(3) tree._add(4) tree._add(5) tree._add(6) tree._add(7) tree._add(8) tree._add(9) tree._add(10) ans = Solution3().preorderTraversal(tree) print ans ans = Solution3().inorderTraversal(tree) print ans ans = Solution3().postorderTraversal(tree) print ans

Output:

[0, 1, 3, 5, 7, 9, 10, 8, 6, 4, 2] [9, 7, 10, 5, 8, 3, 6, 1, 4, 0, 2] [9, 10, 7, 8, 5, 6, 3, 4, 1, 2, 0]