huhu的小世界

1
// 先序打印所有节点，非递归版
2
public static void preOrder(TreeNode head) {
3
    if (head != null) {
4
        Stack<TreeNode> stack = new Stack<>();
5
        stack.push(head);
6
        while (!stack.isEmpty()) {
7
            head = stack.pop();
8
            System.out.print(head.val + " ");
9
            if (head.right != null) {
10
                stack.push(head.right);
11
            }
12
            if (head.left != null) {
13
                stack.push(head.left);
14
            }
15
        }
16
        System.out.println();
17
    }
18
}

1
// 中序打印所有节点，非递归版
2
public static void inOrder(TreeNode head) {
3
    if (head != null) {
4
        Stack<TreeNode> stack = new Stack<>();
5
        while (!stack.isEmpty() || head != null) {
6
            if (head != null) {
7
                stack.push(head);
8
                head = head.left;
9
            } else {
10
                head = stack.pop();
11
                System.out.print(head.val + " ");
12
                head = head.right;
13
            }
14
        }
15
        System.out.println();
16
    }
17
}

1
// 后序打印所有节点，非递归版
2
public static void posOrderOneStack(TreeNode h) {
3
    if (h != null) {
4
        Stack<TreeNode> stack = new Stack<>();
5
        stack.push(h);
6
        // 如果始终没有打印过节点，h就一直是头节点
7
        // 一旦打印过节点，h就变成打印节点
8
        // 之后h的含义：上一次打印的节点
9
        while (!stack.isEmpty()) {
10
            TreeNode cur = stack.peek();
11
            if (cur.left != null && h != cur.left && h != cur.right) {
12
                // 当前节点有左子树
13
                // 并且最近处理过的节点不是它的左孩子，也不是它的右孩子
14
                // 说明左右子树都还没处理到，那么先去处理左子树
15
                stack.push(cur.left);
16
            } else if (cur.right != null && h != cur.right) {
17
                // 左子树已经处理过了，或者根本没有左子树
18
                // 当前有右子树且右子树没有被处理，那么处理右子树
19
                stack.push(cur.right);
20
            } else {
21
                // 左树、右树 没有 或者 都处理过了，那么当前节点就可以访问
22
                // 访问之后把它记录到h里，表示这是最近一次处理完成的节点
23
                System.out.print(cur.val + " ");
24
                h = stack.pop();
25
            }
26
        }
27
        System.out.println();
28
    }
29
}