binary_tree_postorder_traversal

hitzzc · hitzzc · commit c6f6c318a6c2 · 2016-10-12T23:17:56.000+08:00
diff --git a/README.md b/README.md
@@ -128,6 +128,7 @@ Golang solution for leetcode. For each problem, there is a simple *_test.go to t
 #### [142. Linked List Cycle II](https://github.com/hitzzc/go-leetcode/tree/master/linked_list_cycle_II)
 #### [143. reorder list](https://github.com/hitzzc/go-leetcode/tree/master/reorder_list)
 #### [144. binary tree preorder traversal](https://github.com/hitzzc/go-leetcode/tree/master/binary_tree_preorder_traversal)
+#### [145. binary tree postorder traversal](https://github.com/hitzzc/go-leetcode/tree/master/binary_tree_postorder_traversal)
 
 
 
diff --git a/binary_tree_postorder_traversal/binary_tree_postorder_traversal.go b/binary_tree_postorder_traversal/binary_tree_postorder_traversal.go
@@ -0,0 +1,32 @@
+package binary_tree_postorder_traversal
+
+type TreeNode struct {
+	Val   int
+	Left  *TreeNode
+	Right *TreeNode
+}
+
+func postorderTraversal(root *TreeNode) []int {
+	rets := []int{}
+	if root == nil {
+		return rets
+	}
+	stack := []*TreeNode{root}
+	head := root
+	for len(stack) != 0 {
+		node := stack[len(stack)-1]
+		if node.Left == head || node.Right == head || node.Left == nil && node.Right == nil {
+			rets = append(rets, node.Val)
+			stack = stack[:len(stack)-1]
+			head = node
+		} else {
+			if node.Right != nil {
+				stack = append(stack, node.Right)
+			}
+			if node.Left != nil {
+				stack = append(stack, node.Left)
+			}
+		}
+	}
+	return rets
+}
