【手撕代码】二叉树的前序、中序、后序、层级遍历

ゞ浴缸里的玫瑰 2022-02-16 02:07 128阅读 0赞

### **目  录:** ###

**一、递归实现**

1、前序遍历

2、中序遍历

3、后序遍历

**二、非递归实现**

1、层级遍历

2、前序遍历

3、后序遍历

4、中序遍历

--------------------

在面试中常常会问到二叉树的遍历形式：前序、中序、后序以及层级遍历。一般情况下，不会让你手写递归版本，因为确实太简单了，所以，我们需要熟练的掌握非递归版版本。

## 一、递归实现 ##

### 1、前序遍历 ###

public class PreOrderWithRecursion {
    
        public void preOrder(TreeNode root){
            if(root != null){
                // 中、左、右
                System.out.print(root.val + " ");
                preOrder(root.left);
                preOrder(root.right);
            }
        }
    }

### 2、中序遍历 ###

public class InOrder {
    
        public void inOrder(TreeNode root){
            if(root != null){
                inOrder(root.left);
                System.out.print(root.val + " ");
                inOrder(root.right);
            }
        }
    }

### 3、后序遍历 ###

public class postOrderWithRecursion {
    
        public void postOrder(TreeNode root){
            if(root != null){
                postOrder(root.left);
                postOrder(root.right);
                System.out.print(root.val + " ");
            }
        }
    }

前面三种遍历，也就是输出结点数据的位置不同而已，所以很容易，但是如果手写，建议问清楚面试官要求，是在遍历时直接输出还是需要函数返回一个List集合，然后**注意写测试用例代码！**

--------------------

## **二、非递归实现** ##

### 1、层级遍历 ###

*  只需要增加一个队列，将遍历过程中的节点依次放进去，再去按照队列中的节点去遍历它们的子节点。

public class LevelTraverse {
    
        public void levelTraverse(TreeNode root){
            if(root == null){
                return;
            }
    
            // 将节点按照层级结构依次装进队列里
            LinkedList<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while(!queue.isEmpty()){
                TreeNode node = queue.poll();
                System.out.print(node.val + " ");
                if(node.left != null){
                    queue.offer(node.left);
                }
                if(node.right != null){
                    queue.offer(node.right);
                }
            }
        }
    }

### 2、前序遍历 ###

*  前序遍历：中 —> 左 —> 右

分析：处理当前结点，有右孩子先压右孩子进栈，有左孩子再压左孩子进栈，那么这样弹出就会是先左，再右。

*  为什么使用栈而不是队列呢？

二叉树有从上到下和从下到上的路径，所以需要一个结构让它回去，只有栈【队列只能从上到下，回不去】

*  模拟前序遍历元素的进栈出栈过程：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70][]

public class preOrder {
    
        public void prePrder(TreeNode root){
            if(root == null){
                return;
            }
    
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
            while(!stack.isEmpty()){
                //弹出当前节点
                root = stack.pop();
                System.out.print(root.val + " ");
                // 先压右孩子
                if(root.right != null){
                    stack.push(root.right);
                }
                // 再压左孩子
                if(root.left != null){
                    stack.push(root.left);
                }
            }
        }
    }

### 3、后序遍历 ###

*  **后序遍历：左 —> 右  —> 中**

两个栈实现，由先序过程改进而来，先序中左右->中右左->左右中。

*  【分析】：先序中左右，先处理当前结点，然后改为先压左孩子，再压右孩子，那么弹出的顺序就成为了右左【中右左】，利用一个栈即可变为左右中。

public class postOrder {
    
        // 后序遍历非递归版本：前序是：中左右 --> 改进：中右左 --> 栈：左右中
        public void postOrder(TreeNode root){
            if(root == null){
                return;
            }
    
            Stack<TreeNode> stack1 = new Stack<>();
            Stack<TreeNode> stack2 = new Stack<>();  // 用于将：中右左 转换为：左中右
            stack1.push(root);
            // stack1中最后弹出的顺序是：中右左，所以压栈顺序为：先压左再压右
            while(!stack1.isEmpty()){
                root = stack1.pop();
                // stack2的压入顺序即为stack1的弹出顺序：中右左，因此stack2的弹出顺序为：左右中
                stack2.push(root);
                if(root.left != null){
                    stack1.push(root.left);
                }
                if(root.right != null){
                    stack1.push(root.right);
                }
            }
    
            // 弹出stack2中的元素
            while(stack2.isEmpty()){
                System.out.print(stack2.pop().val + " ");
            }
        }
    }

### 4、中序遍历 ###

*  **中序遍历： 左 —> 中  —> 右**

当前节点会把自己的左边界一次性都压到栈里，然后依次弹出，直到遇到一个有右孩子的节点，处理它的右孩子，这样就模拟了“左、中、右”这样的一个过程。

当前节点为空，从栈拿一个打印，当前节点向右移动。当前节点不为空，当前节点压入栈，当前节点往左移动。

public class InOrder {
    
        public void inOrder(TreeNode root){
            if(root == null){
                return;
            }
    
            Stack<TreeNode> stack = new Stack<>();
            // 压一绺左边界，再从尾端依次往外弹，弹出一个节点，再去遍历它的右孩子。这个过程就模拟了：左、中、右这个过程
            // 需要判断head是否为null，是因为后序不同于先序和中序，它是在循环中将root才压入栈的
            while(!stack.isEmpty() || root != null){
                if(root != null){
                    // 一压压一绺左边界
                    while(root != null){
                        stack.push(root);
                        root = root.left;   // 遍历左边界节点
                    }
                }else{
                    // 当前节点为空时，说明上面已经压完了一绺左节点，弹出当前节点（中点），再处理右边
                    root = stack.pop();
                    System.out.print(root.val + " ");
                    root = root.right;
                }
            }
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70]: /images/20220216/fde42988e8814f6fb9329a8d8904a65f.png