题目

给定一个二叉树，返回它的 后序 遍历。

示例:

  1. 输入: [1,null,2,3]  
  2.    1
  3.     \
  4.      2
  5.     /
  6.    3 
  8. 输出: [3,2,1]

方案一（递归）

  1. /**
  2.  * Definition for a binary tree node.
  3.  * type TreeNode struct {
  4.  *     Val int
  5.  *     Left *TreeNode
  6.  *     Right *TreeNode
  7.  * }
  8.  */
  9. func postorderTraversal(root *TreeNode) []int {
  10.     ret := []int{}
  11.     if root != nil {
  12.         ret = append(postorderTraversal(root.Left), postorderTraversal(root.Right)...)
  13.         ret = append(ret, root.Val)
  14.     }
  16.     return ret
  17. }

方案二（迭代）

  1. /**
  2.  * Definition for a binary tree node.
  3.  * type TreeNode struct {
  4.  *     Val int
  5.  *     Left *TreeNode
  6.  *     Right *TreeNode
  7.  * }
  8.  */
  9. func postorderTraversal(root *TreeNode) []int {
  10.     stack := []*TreeNode{root}
  11.     visited := map[*TreeNode]bool{}
  12.     ret := []int{}
  13.     for len(stack) > 0 {
  14.         node := stack[len(stack) - 1]
  15.         stack = stack[:len(stack) - 1]
  16.         if _, ok := visited[node]; ok {
  17.             ret = append(ret, node.Val)
  18.             continue
  19.         }
  20.         if node != nil {
  21.             visited[node] = true
  22.             stack = append(stack, node)
  23.             stack = append(stack, node.Right)
  24.             stack = append(stack, node.Left)
  25.         }
  26.     }
  28.     return ret
  29. }

不需要 **visited** 的迭代：

  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None
  8. class Solution:
  9.     def postorderTraversal(self, root: TreeNode) -> List[int]:
  10.         if not root:
  11.             return []
  13.         stack, res = [root], []
  14.         while stack:
  15.             node = stack.pop()
  16.             res.append(node.val)
  17.             if node.left:
  18.                 stack.append(node.left)
  19.             if node.right:
  20.                 stack.append(node.right)
  22.         return res[::-1]

原文

https://leetcode-cn.com/explore/learn/card/data-structure-binary-tree/2/traverse-a-tree/3/
https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/er-cha-shu-de-hou-xu-bian-li-by-leetcode/