思路
相当于preorder traversal的逆过程。
关键
- 逆过程1：巧用LinkedList的addFirst方法，先pop的节点实际上为输出中靠后的节点。
- 逆过程2：新pop的节点既然在输出中更靠后，因此让right节点先pop，即先是left节点入栈，后是right节点入栈。
...
while (!stack.empty()) {
cur = stack.pop();
rst.addFirst(cur.val);
if (cur.left != null) stack.push(cur.left);
if (cur.right != null) stack.push(cur.right);
}
...
