视频:https://www.bilibili.com/video/BV1Gb4y1W79d/
TreeNode
public class TreeNode {
public TreeNode(int data) {
this.data = data;
}
public int data;
public TreeNode left;
public TreeNode right;
}
Main函数
public class Test {
TreeNode root = new TreeNode(1);
public static void main(String[] args) {
Test test = new Test();
test.initTree(test.root);
test.postOrder(test.root);
}
private void postOrder(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode current = root;
TreeNode lastVisitNode = null;
while (current != null) {
stack.push(current);
current = current.left;
}
while (!stack.empty()) {
TreeNode stackPopNode = stack.pop();
if (stackPopNode.right != null && stackPopNode.right != lastVisitNode) {
stack.push(stackPopNode);
current = stackPopNode.right;
while (current != null) {
stack.push(current);
current = current.left;
}
} else {
System.out.println(stackPopNode.data);
lastVisitNode = stackPopNode;
}
}
}
private void initTree(TreeNode root) {
TreeNode node2 = new TreeNode(2);
TreeNode node3 = new TreeNode(3);
TreeNode node4 = new TreeNode(4);
TreeNode node5 = new TreeNode(5);
TreeNode node6 = new TreeNode(6);
TreeNode node7 = new TreeNode(7);
TreeNode node8 = new TreeNode(8);
TreeNode node9 = new TreeNode(9);
TreeNode node10 = new TreeNode(10);
TreeNode node11 = new TreeNode(11);
TreeNode node12 = new TreeNode(12);
root.left = node2;
root.right = node3;
node2.left = node4;
node2.right = node5;
node3.left = node6;
node3.right = node7;
node4.left = node8;
node4.right = node9;
node5.left = node10;
node5.right = node11;
node6.left = node12;
}