前序、中序、后续遍历二叉树的非递归实现

昨天发了前序、中序、后序遍历二叉树通用公式这篇文章

转发到一个号称人均leetcode100道题的群之后

受到了如下鄙视

但是技不如人，我也没办法刷到平均数

那就发一版非递归版的，接着搬砖努力吧

对于遍历二叉树这种数据结构，最直觉的思路就是使用递归或者栈进行辅助

节点出栈的顺序即为遍历的顺序

以下三种算法均基于栈这种数据结构实现

1. 前序遍历

1.1 思路

前序遍历的公式是“中左右”

即先遍历中间，再遍历左边，最后遍历右边

a、可考虑让根节点先入站，然后将根节点出栈

b、判断出栈的节点是否存在右、左节点，如果存在，则将右、左节点入栈

c、然后再出栈栈顶元素

d、并判断出栈的节点是否存在右、左节点，如果存在，则将右、左节点入栈

循环c、d操作，直到栈内无元素

1.2 图解

将A压入栈

将栈顶元素A弹出

判断A存在右、左节点，所以依次将C、B节点压入栈

弹出栈顶元素B

并判断B存在右、左元素E、D，所以依次将E、D节点压入栈

弹出栈顶元素D

并判断D不存在右、左元素，所以不做任何处理

弹出栈顶元素E

并判断E存在左元素H，所以将H节点压入栈

弹出栈顶元素H

并判断H不存在右、左元素，所以不做任何处理

弹出栈顶元素C

并判断C存在右、左元素G、F，所以依次将G、F节点压入栈

弹出栈顶元素F

并判断F存在右、左元素I、J，所以依次将I、J节点压入栈

至此已无元素可入栈，依次出栈之后，就是前序遍历的结果了

1.3 代码实现

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) {
        return result;
    }
    Deque<TreeNode> stack = new LinkedList<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode temp = stack.pop();
        result.add(temp.val);
        if (temp.right != null) {
            stack.push(temp.right);
        }
        if (temp.left != null) {
            stack.push(temp.left);
        }
    }
    return result;
}

2. 中序遍历

2.1 思路

中序遍历的规则是“左中右”

即先遍历左边的，再中间（当前节点），最后右边的

所以最先拿的数据应该是最左边的节点

a、先将根节点压入栈

b、判断栈顶元素是否存在左节点，如果存在，则压入栈

c、重复b操作，直到栈顶元素不存在左节点

d、将栈顶元素出栈，并判断出栈元素是否存在右右点，如果存在，则入栈

e、重复c操作，直到栈内无元素

2.2 图解

将A节点（根节点）压入栈，并判断是否存在左节点

依次将左节点压入栈，直到左节点为空

将栈顶元素出栈，并判断出栈元素是否存在右节点

不存在，则接着弹出栈顶元素，并判断出栈元素是否存在右节点

存在，则压入栈，并判断是否存在左节点

存在节点H，则压入栈，并判断是否存在左节点

不存在，则出栈栈顶元素，并判断出栈元素是否存在右节点

不存在，则弹出栈顶元素，并判断是否存在右节点

不存在，则弹出栈顶元素A，并判断是否存在右节点

存在右节点I，则循环判断是否存在左节点

存在则依次将F、I压入栈

I不存在左右节点，所以依次弹出I、F节点

F节点存在右节点J，所以将J压入栈

J不存在左右节点，所以弹出栈顶元素J

弹出栈顶元素C，并判断C是否存在右节点

存在右节点G，所以压入栈

G不存在左右节点，所以弹出栈顶元素G

至此，中序遍历完成

2.3 代码实现

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) {
        return result;
    }
    Deque<TreeNode> stack = new LinkedList<>();
    TreeNode temp = root;
    while (temp != null || !stack.isEmpty()) {
        while (temp != null) {
            stack.push(temp);
            temp = temp.left;
        }
        temp = stack.pop();
        result.add(temp.val);
        temp = temp.right;
    }
    return result;
}

3. 后序遍历

3.1 思路

后序遍历的规则是“左右中”

即先左边，再右边，最终中间节点

a、将A节点（根节点）压入栈

b、判断栈顶元是否存在左右节点，如果都不存在，则出栈栈顶元素 c、如果存在右节点，则将右节点压入栈，并断开栈顶元素与右节点的连接，并将右节点压入栈

c、如果存在左节点，则将左节点压入栈，并断开栈顶元素与左节点的连接，并将左节点压入栈

注意：之所以断掉栈顶元素与左右节点的连接，是为了在压入栈判断的时候，不会有节点重复入栈

d、重复b、c、d的操作，直到栈内无元素

3.2图解

首先将根节点A压入栈

判断栈顶元素A存在左右节点，则将右左节点依次入栈

并断开与左右节点的连接

判断栈顶元素B存在左右节点，则将右左节点依次入栈

并断开与左右节点的连接

判断栈顶元素D不存在左右节点，则出栈栈顶元素

判断栈顶元素E存在左节点，则将左节点压入栈

并断开与左节点的连接

判断栈顶元素H不存在左右节点，则将H节点出栈

判断栈顶元素E不存在左右节点，则将栈顶元素E出栈

然后判断栈顶元素B也不存在左右节点，则将栈顶元素B出栈

（在左右节点入栈的时候连接被断开，所以此时会判断无左右节点）

判断栈顶元素C存在左右节点，则将右左节点依次入栈

并断开与左右节点的连接

判断栈顶元素F存在左右节点，则将右左节点依次入栈

并断开与左右节点的连接

此时，已无元素可进站，依次弹出栈内所有节点

至此，出栈顺序就是后序遍历的结果了

3.3 代码实现

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) {
        return result;
    }
    Deque<TreeNode> stack = new LinkedList<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode temp = stack.peek();
        if (temp.left == null && temp.right == null) {
            result.add(stack.pop().val);
        }
        if (temp.right != null) {
            stack.push(temp.right);
            temp.right = null;
        }
        if (temp.left != null) {
            stack.push(temp.left);
            temp.left = null;
        }
    }
    return result;
}

文/戴先生@2021年5月18日

---end---