# 二叉树的后序遍历 - Binary Tree Postorder Traversal

## 145. 二叉树的后序遍历 - Binary Tree Postorder Traversal

【后序遍历-递归】【后序遍历-迭代】【后序遍历-先序的变异】

``````给定一个二叉树，返回它的 后序 遍历。题目描述

``````

### Example:

``````输入: [1,null,2,3]
1
\
2
/
3

``````

## Solutions

 `````` 1 2 3 4 5 6 7 8 9 10 `````` ``````/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ ``````

### Solution 【后序遍历-递归】 ( 0ms)

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 `````` ``````class Solution { List result =new ArrayList(); public List postorderTraversal(TreeNode root) { loop(root); return result; } /* 单独写递归循环，减少return的次数 */ public void loop(TreeNode node){ if(node==null) return; loop(node.left); loop(node.right); result.add(node.val); } } ``````

### Solution 【后序遍历-迭代】 ( 2ms)

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 `````` ``````class Solution { public List postorderTraversal(TreeNode root) { List result = new ArrayList(); if(root == null) return result; Stack stack = new Stack(); TreeNode pre = null; stack.push(root); while(!stack.isEmpty()){ TreeNode curr = stack.peek(); if((curr.left == null && curr.right == null) || (pre != null && (pre == curr.left || pre == curr.right))){ result.add(curr.val); pre = curr; stack.pop(); }else{/* 先将右结点压栈, 再将左结点入栈 */ if(curr.right != null) stack.push(curr.right); if(curr.left != null) stack.push(curr.left); } } return result; } } ``````

### Solution 【后序遍历-先序的变异】 ( 2ms)

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 `````` ``````class Solution { public List postorderTraversal(TreeNode root) { List result = new ArrayList(); if(root == null) return result; Stack stack = new Stack(); stack.push(root); while(!stack.isEmpty()){ TreeNode node = stack.pop(); if(node.left != null) stack.push(node.left);//和传统先序遍历不一样，先将左结点入栈 if(node.right != null) stack.push(node.right);//后将右结点入栈 result.add(0,node.val); //逆序添加结点值 } return result; } } ``````