590: use stack instead of recursive

legolas.zhan · legolas.zhan · commit ce0e1901ef0d · 2024-08-26T13:44:10.000+08:00
diff --git a/leetcode/tree/postorder.go b/leetcode/tree/postorder.go
@@ -27,18 +27,35 @@ type Node struct {
 }
 
 func postorder(root *Node) []int {
-	var helper func(root *Node, ans *[]int)
-	helper = func(root *Node, ans *[]int) {
-		if root == nil {
-			return
-		}
-		for _, child := range root.Children {
-			helper(child, ans)
+	// var helper func(root *Node, ans *[]int)
+	// helper = func(root *Node, ans *[]int) {
+	// 	if root == nil {
+	// 		return
+	// 	}
+	// 	for _, child := range root.Children {
+	// 		helper(child, ans)
+	// 	}
+	// 	*ans = append(*ans, root.Val)
+	// }
+
+	// ans := []int{}
+	// helper(root, &ans)
+	// return ans
+
+	ans := []int{}
+	stack := []*Node{root}
+	for len(stack) != 0 {
+		cur := stack[len(stack)-1]
+		ans = append(ans, cur.Val)
+		stack = stack[:len(stack)-1]
+		for _, child := range cur.Children {
+			stack = append(stack, child)
 		}
-		*ans = append(*ans, root.Val)
 	}
 
-	ans := []int{}
-	helper(root, &ans)
+	for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
+		ans[i], ans[j] = ans[j], ans[i]
+	}
+
 	return ans
 }
