145. Binary Tree Postorder Traversal ⭐

Easy

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
}