二叉树的遍历（前序、中序、后序）Java详解与代码实现

不念不忘少年蓝@ 2023-09-25 23:52 12阅读 0赞

## 递归遍历 ##

### 前序，中序，后序 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    
    //前序遍历
    class Solution {
        
        public List<Integer> preorderTraversal(TreeNode root) {
        
            List<Integer> res=new ArrayList<>();
            preorder(root,res);
            return res;
        }
        void preorder(TreeNode root, List<Integer> res){
        
            if(root==null){
        
                return;
            }
            res.add(root.val);
            preorder(root.left,res);
            preorder(root.right,res);
        }
    }
    //中序遍历
    class Solution {
        
        public List<Integer> inorderTraversal(TreeNode root) {
        
            List<Integer> res=new ArrayList<>();
            inorder(root,res);
            return res;
        }
        void inorder(TreeNode root,List<Integer> res){
        
            if(root==null){
        
                return;
            }
            inorder(root.left,res);
            res.add(root.val);
            inorder(root.right,res);
            
        }
    }
    //后序遍历
    class Solution {
        
        public List<Integer> postorderTraversal(TreeNode root) {
        
            List<Integer> res=new ArrayList<>();
            postOrder(root,res);
            return res;
        }
        void postOrder(TreeNode root,List<Integer> res){
        
            if(root==null){
        
                return;
            }
            postOrder(root.left,res);
            postOrder(root.right,res);
            res.add(root.val);
        }
    }

**这三个遍历，理解起来都是差不多的**

> 以前序遍历为例
> 
> 以每一个树或子树的根节点和List集合作为函数的参数返回值类型是void.
> 
> 如果碰到每一个树或子树的根节点是空，就结束递归，结束函数
> 
> 否则，先把根节点的值收入集合，再把左右结点(子树)的值收入集合
> 
> 最后调用函数之后，返回这个集合

## 迭代法（非递归） ##

### 前序，后序 ###

#### **前序** ####

用栈模拟(实现)递归

> 先把树或某一子树的根节点入栈，然后，进入数组
> 
> 再分别把右左子树的根节点入栈，然后分别将二者进入数组（右先入栈左后入栈，才能保证左先入数组，右后入数组）
> 
> 这样左中右结点进入数组的顺序为：中左右

#### 后序 ####

以此类推，入栈的顺序为中左右，这样入数组的顺序为中右左，然后再将数组逆序对调

这样，数组输出的顺序就是左右中

**要注意的是，Java中，List没有将集合元素逆序对调的方法，所以，要使用Collections的reverse方法**

### 中序 ###

> 这里的遍历方式和前序后序不一样了
> 
> 前序后序差不多算是遍历到哪个结点就处理哪个节点。这里不一样，这里是先处理左节点，左子树的左子树的左子树的左……左节点……所以，要先遍历到最左的左节点，然后再看最左节点的根节点然后他的根结点的右子节点。
> 
> 这里还用到了一个指针来指向要处理的树的结点

## 二叉树迭代遍历法的统一写法风格 ##

我们以中序遍历为例，在[二叉树：听说递归能做的，栈也能做！ (opens new window)][_opens new window]中提到说使用栈的话，**无法同时解决访问节点（遍历节点）和处理节点（将元素放进结果集）不一致的情况**。

**那我们就将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。**

如何标记呢，**就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。** 这种方法也可以叫做标记法

Java： 迭代法前序遍历代码如下:

class Solution {
        
        public List<Integer> preorderTraversal(TreeNode root) {
        
            List<Integer> result = new LinkedList<>();
            Stack<TreeNode> st = new Stack<>();
            if (root != null) st.push(root);
            while (!st.empty()) {
        
                TreeNode node = st.peek();
                if (node != null) {
        
                    st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                    if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
                    if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）
                    st.push(node);                          // 添加中节点
                    st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。
                    
                } else {
         // 只有遇到空节点的时候，才将下一个节点放进结果集
                    st.pop();           // 将空节点弹出
                    node = st.peek();    // 重新取出栈中元素
                    st.pop();
                    result.add(node.val); // 加入到结果集
                }
            }
            return result;
        }
    }

迭代法中序遍历代码如下:

class Solution {
        
    public List<Integer> inorderTraversal(TreeNode root) {
        
            List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
        
            TreeNode node = st.peek();
            if (node != null) {
        
                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
                st.push(node);                          // 添加中节点
                st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。
    
                if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）
            } else {
         // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop();
                result.add(node.val); // 加入到结果集
            }
        }
        return result;
    }
    }

迭代法后序遍历代码如下:

class Solution {
        
       public List<Integer> postorderTraversal(TreeNode root) {
        
            List<Integer> result = new LinkedList<>();
            Stack<TreeNode> st = new Stack<>();
            if (root != null) st.push(root);
            while (!st.empty()) {
        
                TreeNode node = st.peek();
                if (node != null) {
        
                    st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                    st.push(node);                          // 添加中节点
                    st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。
                    if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
                    if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）         
                                   
                } else {
         // 只有遇到空节点的时候，才将下一个节点放进结果集
                    st.pop();           // 将空节点弹出
                    node = st.peek();    // 重新取出栈中元素
                    st.pop();
                    result.add(node.val); // 加入到结果集
                }
            }
            return result;
       }
    }

[_opens new window]: https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BF%AD%E4%BB%A3%E9%81%8D%E5%8E%86.html