## Tree - 145. Binary Tree Postorder Traversal

Updated on with 0 views and 0 comments

145. Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes' values.

Example:

Input: [1,null,2,3]
1

2
/
3
Output: [3,2,1]

Follow up: Recursive solution is trivial, could you do it iteratively?

go：

``````/**

* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/

/* // recursive
func postorderTraversal(root *TreeNode) []int {
var res []int

recursive(root, &res)

return res
}

func recursive(root *TreeNode, res *[]int) {
if root == nil {
return
}

recursive(root.Left, res)
recursive(root.Right, res)
*res = append(*res, root.Val)
}
*/

// iteratively
func postorderTraversal(node *TreeNode) []int {

var res []int
var stack []*TreeNode
var visited *TreeNode

for node != nil || len(stack) != 0 {
for node != nil {
stack = append(stack, node)
node = node.Left
}

// 访问栈顶元素
node = stack[len(stack) - 1]

if node.Right != nil && node.Right != visited {
node = node.Right
} else {
// 父节点的右子树被访问过了，父节点出栈
stack = stack[:len(stack) - 1]
res = append(res, node.Val)
visited = node
node = nil  // 保证不会再被入栈
}
}

return res
}
``````