Given the root of a binary tree, return the postorder traversal of its nodes' values.
Example 1:
Input: root = [1,null,2,3]
Output:
[3,2,1]
Example 2:
Input: root = []
Output:
[]
Example 3:
Input: root = [1]
Output:
[1]
Constraints:
The number of the nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100
Follow up: Recursive solution is trivial, could you do it iteratively?
解題
這題和 144 是姐妹題。
Recursive 解法：
/**
* Definition for a binary tree node .
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func postorderTraversal(root *TreeNode) []int {
res := make([]int, 0)
var helper func(*TreeNode)
helper = func(root *TreeNode) {
if root == nil { return }
helper(root.Left)
helper(root.Right)
res = append(res, root.Val)
}
helper(root)
return res
}
使用 stack 與 for loop
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func postorderTraversal(root *TreeNode) []int {
ans := make([]int, 0)
if root == nil { return ans }
stack := make([]*TreeNode, 0)
stack = append(stack, root)
for len(stack) > 0 {
node := stack[len(stack)-1]
if node.Right == nil && node.Left == nil {
stack = stack[:len(stack)-1]
ans = append(ans, node.Val)
}
if node.Right != nil {
stack = append(stack, node.Right)
node.Right = nil
}
if node.Left != nil {
stack = append(stack, node.Left)
node.Left = nil
}
}
return ans
}
