Leetcode-Java/leetcode/solution/src/BinaryTreePostorderTraversal.java at master · lxzgitcode/Leetcode-Java

Repository navigation

import java.util.*;

public class BinaryTreePostorderTraversal {

/**

* 先序是中左右，中序是左中右，后序是左右中，所以我们可以给先序调整一下改成中右左，然后倒过来就成了左右中

* @param root

* @return

// 这里虽然最后的结果返回的是对的，但真正访问节点的顺序是不对的，root并不是最后访问的

public List<Integer> postorderTraversal(TreeNode root) {

List<Integer> results = new LinkedList<>();

Deque<TreeNode> stack = new ArrayDeque<TreeNode>();

while (!stack.isEmpty() || root != null) {

if (root != null) {

stack.push(root);

results.add(0, root.val);

root = root.right;

} else {

root = stack.pop().left;

}

return results;

}

// root为null表示栈顶的左子树都访问完了，该看右子树了

public List<Integer> postorderTraversal2(TreeNode root) {

List<Integer> result = new ArrayList<>();

Stack<TreeNode> stack = new Stack<>();

for (TreeNode last = null; !stack.isEmpty() || root != null; ) {

if (root != null) {

stack.push(root);

root = root.left;

} else {

TreeNode peek = stack.peek();

if (peek.right != null && last != peek.right) {

root = peek.right; // 只有这里要设置root

} else {

result.add(peek.val);

last = stack.pop();

// 此时root仍为null

}

return result;

}