给定一个二叉树，返回它的 后序 遍历。
示例:
输入: [1,null,2,3]
1
2
/
3
输出: [3,2,1]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解：
思路一：
递归，代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
|
// 递归
ArrayList <Integer> list = new ArrayList<>();
public List<Integer> postorderTraversalRecuisive(TreeNode root) {
if (root == null) return list;
postorderTraversalRecuisive(root.left);
postorderTraversalRecuisive(root.right);
list.add(root.val);
return list;
}
|
思路二：
迭代：
稿纸上分析如下 ：
代码如下：
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
|
// 非递归
public List<Integer> postorderTraversal(TreeNode root) {
ArrayList <Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if (root == null) return list;
stack.push(root);
TreeNode pre = null;
while (!stack.isEmpty()){
TreeNode node = stack.peek();
if ((node.left == null && node.right == null)|| (pre != null && (pre == node.left || pre == node.right))) {
// 叶子节点 或者 上一个访问的节点是此节点的子节点时 出栈
list.add(node.val);
pre = node;
stack.pop();
}else{
// 右子节点不为空
if (node.right != null) stack.push(node.right);
// 左子节点不为空
if (node.left != null) stack.push(node.left);
}
}
return list;
}
|