二叉树的遍历（递归、非递归、Morris Traversal）

二叉树的遍历

原文链接：https://www.leahy.club/archives/%E7%AE%97%E6%B3%95%E4%B8%8E%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%81%8D%E5%8E%86

1. 综述

在二叉树中，搜索(Search)和遍历(Traversal)本质上是一致的，在代码层面差别也不大。

那么，二叉树的遍历(Traversal)可以主要分为深度优先搜索(Deep First Search， DFS)和广度优先遍历(Breadth First Search， BFS)。

深度优先遍历可以分为前序遍历(preOrderTraversal)、中序遍历(inOrderTraversal)、后序遍历(postOrderTraversal)。

深度优先的三种遍历主要有三种实现方式：递归、栈+循环、Morris Traversal。

2. 遍历的递归实现

2.1 前序遍历

public void preOrder(Node root) {
    if (root == null)
        return;
    System.out.println(root.val);
    preOrder(root.left);
    preOrder(root.right);
}

2.2 中序遍历

public void inOrder(Node root) {
    if (root == null)
        return;
    inOrder(root.left);
    System.out.println(root.val);
    inOrder(root.right);
}

2.3 后序遍历

public void postOrder(Node root) {
    if (root == null)
        return;
    postOrder(root.left);
    postOrder(root.right);
    System.out.println(root.val);
}

总结：采用递归的方式是最简单的方式，但是时间复杂度和空间复杂度都是 $O\left(n\right)$O(n)。如果树的节点数很大，采用递归的方式很容易导致内存的溢出。

3. 遍历的循环实现

3.1 前序遍历

/** *对于任一节点p: *1)若节点P不为空，访问节点P，并入栈； *2)判断节点P的左孩子是否为空。若为空则取栈顶元素出栈，并将栈顶元素的右孩子作为当前节点P,循环至1；若不为空则，P更新为P节点的左孩子。 *3)知道P为空或者栈为空。 * **/

public void preOrder(Node root) {
    if (root = null)
        return;
    
    Stack stack = new Stack();
    Node cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            System.out.println(cur.val);
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        cur = cur.right;
    }
}

3.2 中序遍历

/** *对于任一节点p: *1)若节点P不为空，将节点P入栈； *2)判断节点P的左孩子是否为空。若为空则取栈顶元素出栈，并访问出栈元素，最后将栈顶元素的右孩子作为当前节点P,循环至1；若不为空则，P更新为P节点的左孩子。 *3)知道P为空或者栈为空。 * *与前序遍历唯一的不同在于访问元素的代码位置 * **/

public void inOrder(Node root) {
    if (root == null)
        return;
    Stack stack = new Stack();
    Node cur = root;
    
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        System.out.println(cur.val);
        cur = cur.right;
    }
}

3.3 后序遍历

/** 要保证根节点在左孩子和右孩子访问之后才能访问，因此对于任一节点P先将其入栈。如果P不存在左右子节点，则可以直接访问； 或者P存在左或者右孩子，但是其左右孩子均被访问过了，则同样可以直接访问该节点P; 若非上述两种情况，则先将P节点的右孩子入栈，再将左孩子入栈，保证左孩子在右孩子之前被访问，且都在根节点之前访问。 **/
public void postOrder(Node root) {
    if (root == null)
        return;
    Stack stack = new Stack();
    Node cur = root;
    Node pre = null; //记录前一次访问的节点
    
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        //左孩子为空且右孩子为空或者左孩子为空，右孩子以及被访问过了
        if (cur.right == null || pre == cur.right) {
            System.out.println(cur.val);
            pre = cur;
            cur = null;
        }
        //左孩子为空，右孩子不为空
        else {
            stack.push(cur);
            cur = cur.right;
        }
    }
}

总结：时间和空间复杂度依旧是 $O\left(n\right)$O(n)。

4. Morris Traversal

Morris traversal可以实现时间复杂度 $O\left(n\right)$O(n)，空间复杂度为 $O\left(1\right)$O(1)。

要使用O(1)空间进行遍历，最大的难点在于，遍历到子节点的时候怎样重新返回到父节点（假设节点中没有指向父节点的p指针），由于不能用栈作为辅助空间。为了解决这个问题，Morris方法用到了线索二叉树（threaded binary tree）的概念。在Morris方法中不需要为每个节点额外分配指针指向其前驱（predecessor）和后继节点（successor），只需要利用叶子节点中的左右空指针指向某种顺序遍历下的前驱节点或后继节点就可以了。

Morris只提供了中序遍历的方法，在中序遍历的基础上稍加修改可以实现前序，而后续就要再费点心思了。所以先从中序开始介绍。

4.1 中序遍历

步骤：

对于任一节点P:

1. 如果P的左孩子为空，则访问P并将P更新为其右孩子；

2. 如果P的左孩子不为空，在P的左子树中找到P节点的中序遍历下的前驱节点

   a) 如果前驱节点的右孩子为空，将它的右孩子设置为P节点。P节点更新为其左孩子；

   b)如果前驱节点的右孩子为节点P，将前驱节点而当右孩子重新设置为空（恢复树的形状）。输出节点P，并将P节点更新为其右孩子。

3. 重复上述1,2直到P节点为空。

图示：

下图为每一步迭代的结果（从左至右，从上到下），cur代表当前节点，深色节点表示该节点已输出。

代码：

public void inOrder(Node root) {
    if (root == null)
        return;
    Node cur = root;
    Node pre = null;
    
    while (cur != null) {
        if (cur.left == null) {
            System.out.println(cur.val);
        	cur = cur.right;
        } 
        else {
            
            //得到前驱节点
            pre = cur.left
            while (pre.right != null && pre.right != cur) {
                pre = pre.right;
            }
            if (pre.right == null) { //2.a)
                pre.right = cur;
                cur = cur.left;
            }
            else {                  //2.b)
                pre.right = null;
                System.out.println(cur.val);
                cur = cur.right;
            }
        }
    }
}

复杂度分析：

空间复杂度： $O\left(1\right)$O(1) ，因为只用了两个辅助指针。

时间复杂度： $O\left(n\right)$O(n) 。证明时间复杂度为 $O\left(n\right)$O(n) ， 最大的疑惑在于寻找中序遍历下二叉树中所有节点的前驱节点的时间复杂度是多少，即以下两行代码：

1 while (prev->right != NULL && prev->right != cur)
2     prev = prev->right;

直觉上，认为它的复杂度是 $O\left(nlog\right(n\left)\right)$O(nlog(n))，因为找单个节点的前驱节点与树的高度有关。但事实上，寻找所有节点的前驱节点只需要 $O\left(n\right)$O(n) 时间。n个节点的二叉树中一共有n-1条边，整个过程中每条边最多只走2次，一次是为了定位到某个节点，另一次是为了寻找上面某个节点的前驱节点，如下图所示，其中红色是为了定位到某个节点，黑色线是为了找到前驱节点。所以复杂度为 $O\left(n\right)$O(n) 。

4.2 前序遍历

前序遍历与中序遍历相似，代码上只有一行不同，不同就在于输出的顺序。这一点在上述第2节与第3节中描述的前序遍历与中序遍历之间关系的特点是一致的。

步骤：

1. 如果当前节点的左孩子为空，则输出当前节点并将其右孩子作为当前节点。

2. 如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点。

   a) 如果前驱节点的右孩子为空，将它的右孩子设置为当前节点。**输出当前节点（在这里输出，这是与中序遍历唯一一点不同）。**当前节点更新为当前节点的左孩子。

   b) 如果前驱节点的右孩子为当前节点，将它的右孩子重新设为空。当前节点更新为当前节点的右孩子。

3. 重复以上1、2直到当前节点为空。

图示：

代码：

public void inOrder(Node root) {
    if (root == null)
        return;
    Node cur = root;
    Node pre = null;
    
    while (cur != null) {
        if (cur.left == null) {
            System.out.println(cur.val);
        	cur = cur.right;
        } 
        else {
            
            //得到前驱节点
            pre = cur.left
            while (pre.right != null && pre.right != cur) {
                pre = pre.right;
            }
            if (pre.right == null) { //2.a)
                System.out.println(cur.val);
                pre.right = cur;
                cur = cur.left;
            }
            else {                  //2.b)
                pre.right = null;
                cur = cur.right;
            }
        }
    }
}

4.3 后序遍历

使用Morris Traversal实现后序遍历过于麻烦，不常用。

5. 广度优先遍历

二叉树的广度优先遍历一般借用一个辅助队列来实现。

public void BFS(Node root) {
    if (root == null)
        return;
    Queue queue = new Queue();
    queue.add(root);
    
    while (!queue.isEmpty()) {
        Node cur = queue.remove();
        System.out.println(cur.val);
        
        if (cur.left != null)
            queue.add(cur.left);
        if (cur.right != null)
            queue.add(cur.right);
    }
}

时间、空间复杂度均是 $O\left(n\right)$O(n)。

参考链接：

[1]https://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html

[2]https://blog.csdn.net/qq_43152052/article/details/90111095