145.二叉树的后序遍历

链接：145.二叉树的后序遍历
难度：Easy
标签：栈、树、深度优先搜索、二叉树
简介：给定一个二叉树，返回它的 后序 遍历。

题解 1 - java

• 编辑时间：2020-02-21
• 内存消耗：37.7MB
• 编程语言：java
• 解法介绍：递归。

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list=new LinkedList<Integer>();
        if(root!=null) {
        	postorder(root, list);
        }
        return list;
    }
    public void postorder(TreeNode node,List<Integer> list) {
    	if(node.left!=null)postorder(node.left, list);
    	if(node.right!=null)postorder(node.right, list);
    	list.add(node.val);
    }
}

题解 2 - java

• 编辑时间：2020-02-21
• 执行用时：1ms
• 内存消耗：38.1MB
• 编程语言：java
• 解法介绍：迭代。

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> list=new LinkedList<Integer>();
        if(root==null)return list;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while(!stack.isEmpty()) {
        	TreeNode node = stack.pop();
        	list.addFirst(node.val);
        	if(node.left!=null)stack.push(node.left);
        	if(node.right!=null)stack.push(node.right);
        }
        return list;
    }
}

题解 3 - typescript

• 编辑时间：2020-09-29
• 执行用时：84ms
• 内存消耗：39.6MB
• 编程语言：typescript
• 解法介绍：递归。

function postorderTraversal(root: TreeNode | null): number[] {
  const ans: number[] = [];
  postOrder(root);
  return ans;
  function postOrder(root: TreeNode | null): void {
    if (root === null) return;
    root.left && postOrder(root.left);
    root.right && postOrder(root.right);
    ans.push(root.val);
  }
}

题解 4 - typescript

• 编辑时间：2020-09-29
• 执行用时：96ms
• 内存消耗：39.8MB
• 编程语言：typescript
• 解法介绍：迭代遍历。

function postorderTraversal(root: TreeNode | null): number[] {
  const ans: number[] = [];
  if (root === null) return [];
  const used = new Set<TreeNode>();
  const stack: TreeNode[] = [root];
  while (stack.length !== 0) {
    const node = stack.pop()!;
    if (used.has(node)) ans.push(node.val);
    else {
      stack.push(node);
      node.right && stack.push(node.right);
      node.left && stack.push(node.left);
      used.add(node);
    }
  }
  return ans;
}

题解 5 - typescript

• 编辑时间：2021-03-19
• 执行用时：100ms
• 内存消耗：39.5MB
• 编程语言：typescript
• 解法介绍：递归遍历。

function postorderTraversal(root: TreeNode | null): number[] {
  const ans: number[] = [];
  const preorder = (node: TreeNode | null): void => {
    if (node === null) return;
    preorder(node.left);
    preorder(node.right);
    ans.push(node.val);
  };
  preorder(root);
  return ans;
}

题解 6 - c

• 编辑时间：2021-11-27
• 内存消耗：5.7MB
• 编程语言：c
• 解法介绍：递归。

// 先递归左，再递归右，再计算当前节点
void order(struct TreeNode *root, int *arr, int *idx){
    if (!root) return ;
    order(root->left, arr, idx);
    order(root->right, arr, idx);
    arr[(*idx)++] = root->val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize){
    int *arr = (int *)malloc(sizeof(int) * 100);
    *returnSize = 0;
    order(root, arr, returnSize);
    return arr;
}

题解 7 - python

• 编辑时间：2024-02-12
• 执行用时：42ms
• 内存消耗：16.4MB
• 编程语言：python
• 解法介绍：dfs。

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root: return []
        return self.postorderTraversal(root.left) + self.postorderTraversal(root.right) + [root.val]