树的非递归遍历

发表于 | 分类于

前言

众所周知, 树的遍历主要有四种方法: 前序遍历, 中序遍历, 后序遍历和层序遍历. 其中, 前中后序遍历最简洁的实现方法就是递归实现, 以二叉树为例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 前序遍历递归实现的伪代码
void preOrder(Node root) {
    if (root == null) return;
    visit(root);
   	preOrder(root.left);
    preOrder(root.right);
}

// 中序遍历递归实现的伪代码
void inOrder(Node root) {
    if (root == null) return;
    inOrder(root.left);
    visit(root);
    inorder(root.right);
}

// 后序遍历递归实现的伪代码
void postOrder(Node root) {
    if (root == null) return;
    postOrder(root.left);
    postOrder(root.right);
    visit(root);
}

而非递归的实现则会使用栈来代替递归, 因为计算机内部也是用栈来实现递归的.

中序遍历

为了方便理解, 先从中序遍历开始讲起.

回忆一下, 二叉树中中序遍历的顺序是: 左子树 - 根 - 右子树, 那么我们一开始肯定要走到树的最左下角, 并将经过的结点进行入栈

1
2
3
4
5
Node p = root;
while (p != null) {
    stack.push(p)
    p = p.left;
}

从图中可以看见, 当p左边的路径走到尽头之后, 栈顶结点为3, 且有两种情况:

  1. 没有右儿子
  2. 有右儿子

对于情况1, 栈顶结点没有右儿子, 直接出栈栈顶结点, 然后访问, p指向右儿子(为空)

1
2
3
p = stack.pop();
visit(p);
p = p.right; // null

对于情况2, 栈顶结点有右儿子, 直接出栈栈顶结点, 然后访问, p指向右儿子(不为空)

1
2
3
p = stack.pop();
visit(p);
p = p.right; // not null

上面两个代码将两种情况都统一表示了, 那么如何去区分两种情况呢? 方法很简单, 只要在迭代里面增加对p是否为null进行判断就可以了.

  • 如果p为null, 说明栈顶结点没有右子树, 那么我们继续处理栈的下一个结点
  • 如果p不为null, 说明栈顶结点有右子树, 那么我们需要对这个右子树进行一遍上面所说的操作, 也就是说需要走到右子树的”最左边”. 到达”最左边”之后, 继续进行我们所说的这些处理.

伪代码如下:

1
2
3
4
5
6
7
8
9
10
while (some condition) {
    if (p != null) {  // p不为空, 则需要走到"最左边"
        stack.push(p);  // 走的过程中将路过的结点入栈
        p = p.left;
    } else {   // p为空, 那么处理栈剩下的结点
    	p = stack.pop();  // 出栈
        visit(p);  // 访问结点
        p = p.right;  // 指向p的右子树, 留到下一个循环去判断p是否为空
    }
}

那么代码的大体框架已经写好了, 最后只剩下while()循环里面的条件了, 很明显当栈空且p也为null的情况下需要中止循环, 已经遍历完了. (注意: 当栈为空时, 不一定遍历结束, 因为p不为空的话, 说明还有右子树没有遍历). 转换一下逻辑, 也就是说当栈不空或者p不为null的时候可以继续循环. 完整的伪代码如下:

1
2
3
4
5
6
7
8
9
10
while (p != null || !stack.isEmpty()) {
    if (p != null) {  // p不为空, 则需要走到"最左边"
        stack.push(p);  // 走的过程中将路过的结点入栈
        p = p.left;
    } else {   // p为空, 那么处理栈剩下的结点
    	p = stack.pop();  // 出栈
        visit(p);  // 访问结点
        p = p.right;  // 指向p的右子树, 留到下一个循环去判断p是否为空
    }
}

OK! 伪代码写出来了, 那我们来实践一下吧! Leetcode中的94.二叉树的中序遍历这一题就是

考察二叉树中序遍历的迭代实现, 根据上面所说的, 可以很轻松地写下代码(使用Java实现)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode p = root;
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p = p.left;
            } else {
                p = stack.pop();
                result.add(p.val);
                p = p.right;
            }
        }
        return result;
    }
}

前序遍历

前序遍历和中序遍历思想是类似的, 中序遍历需要先入栈再访问, 而先序遍历则是访问再入队. 这样就会满足: 根结点 - 左子树 - 右子树

1
2
3
4
5
6
7
8
9
10
while (p != null || stack.isEmpty()) {
    if (p !=  null) {  // p 不为空, 则需要走到"最左边"
        visit(p); // 在入栈之前进行访问结点
        stack.push(p);
        p = p.left;
    } else {
        p = stack.pop();  // 出栈
        p = p.right;  // 指向p的右子树, 留到下一个循环去判断p是否为空
    }
}

OK! 同样地, 去Leetcode实践一下->二叉树的前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        ArrayList<Integer> result = new ArrayList<>();
        TreeNode p = root;
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                result.add(p.val);
                stack.push(p);
                p = p.left;
            } else {
                p = stack.pop();
                p = p.right;
            }
        }
        return result;
    }
}

后序遍历

后序遍历的情况会更复杂一些, 因为后序遍历的顺序是: 左子树 - 右子树 - 根结点. 所以取出栈顶元素之后, 栈顶元素如果:

  • 位于左子树中, 需要跳过根结点, 直接访问右子树
  • 位于右子树中, 访问根结点

有一种实现方法是在树的结构中增加标记来判断是否需要跳过根结点. 但是我们可以使用更简便地方法, 就是将顺序颠倒一下.

后序遍历的顺序颠倒过来就是: 根结点 - 右子树 - 左子树.

仔细观察一下, 是不是很像前序遍历的顺序? 前序遍历中的顺序是: 根结点 - 左子树 - 右子树.

我们只需要将前序遍历代码中的left和right交换一下, 就可以得到: 根结点 - 右子树 - 左子树的顺序, 最后再将结果反转, 就可以得到”左子树 - 右子树 - 根结点”的顺序. 而实现的时候只需要将结点添加到List的头部就可以了

1
2
3
4
5
6
7
8
9
10
11
while (p != null || stack.isEmpty()) {
    if (p !=  null) {  // p 不为空, 则需要走到"最右边"
        result.addFirst(p); // 在入栈之前进行访问结点
        stack.push(p);
        p = p.right;  // 
    } else {
        p = stack.pop();  // 出栈
        p = p.left;  // 指向p的左子树, 留到下一个循环去判断p是否为空
    }
}
System.out.println(result);

OK! 去Leetcode实践一下->二叉树的后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> result = new LinkedList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode p = root;
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                result.addFirst(p.val);
                stack.push(p);
                p = p.right;
            } else {
                p = stack.pop();
                p = p.left;
            }
        }
        return result;
    }
}

N叉树的遍历

既然二叉树的遍历已经搞清楚了, 那么我们接下来就推广到N叉树吧. 要注意的是N叉树的中序遍历暂无明确的定义, 所以这里我们只讨论N叉树的前序遍历和后序遍历.

N叉树遍历的递归实现

先来看看前序遍历和后序遍历的递归伪代码实现吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// N叉树的前序遍历
void preOrder(Node root) {
    if (root == null) return;
    visit(root)
    for (Node child : root.children) {
        preorder(child);
    }
}

// N叉树的后序遍历
void postOrder(Node root) {
    if (root == null) return;
    for (Node child : root.children) {
        postOrder(child);
    }
    visit(root);
}

N叉树前序遍历

  1. 先将根结点入栈
  2. 队中结点出列, 并将结点的值放入结果队列中, 然后将其子结点从右至左的顺序入队(保证下一个结点是最左边的子结点)
  3. 重复第二步直至栈为空

直接在Leetocde上面实现看看! N叉树的前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
    public List<Integer> preorder(Node root) {
        LinkedList<Node> stack = new LinkedList<>();
        LinkedList<Integer> result = new LinkedList<>();
        if (root == null) return result;
        stack.push(root);
        while (!stack.isEmpty()) {
            Node tmpNode = stack.pop();
            result.add(tmpNode.val);
            Collections.reverse(tmpNode.children); // 逆序
            for (Node child : tmpNode.children) {
                stack.push(child);
            }
        }
        return result;
    }
}

N叉树后序遍历

  1. 先将根结点入栈
  2. 取出栈中结点, 并将结点的值放入结果队列的头部, 将其子结点按左到右的顺序入栈
  3. 重复第二步直至栈为空
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public List<Integer> postorder(Node root) {
        LinkedList<Node> stack = new LinkedList<>();
        LinkedList<Integer> output = new LinkedList<>();
        if (root == null) return output;
        stack.add(root);
        while (!stack.isEmpty()) {
            Node tmpNode = stack.pollLast();
            output.addFirst(tmpNode.val);
            for (Node child : tmpNode.children) {
                stack.add(child);
            }
        }
        return output;
    }
}