package com.app.main.LeetCode.tree;
import com.app.main.LeetCode.base.TreeNode;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
*
* 145
*
* hard
*
* https://leetcode.com/problems/binary-tree-postorder-traversal/
*
* Given a binary tree, return the postorder traversal of its nodes' values.
*
* Example:
*
* Input: [1,null,2,3]
* 1
* \
* 2
* /
* 3
*
* Output: [3,2,1]
* Follow up: Recursive solution is trivial, could you do it iteratively?
*
*
* Created with IDEA
* author:Dingsheng Huang
* Date:2019/10/31
* Time:下午8:37
*/
public class BinaryTreePostorderTraversal {
// recursion
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
process(root, result);
return result;
}
private void process(TreeNode root, List<Integer> result) {
if (root != null) {
if (root.left != null) {
process(root.left, result);
}
if (root.right != null) {
process(root.right, result);
}
result.add(root.val);
}
}
// iterator
public List<Integer> postorderTraversal2(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode pre = null;
TreeNode curr = null;
// 按照 根 - 右 - 左的顺序入栈
stack.push(root);
while (!stack.isEmpty()) {
curr = stack.peek();
// 判断当前节点有孩子节点的时候，是否应该入栈，用一个pre临时节点记录
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;
}
}
