树、二叉树的前中后层序遍历（递归、非递归Java实现）

快来打我* 2021-09-22 15:48 256阅读 0赞

### 文章目录 ###

*  1. 二叉树的前中后序遍历（递归，非递归）以及层序遍历
 *   *  1.1 二叉树前中后遍历的递归解法
     *  1.2 二叉树前中后遍历的非递归解法
     *   *  1.2.1 非递归的前序遍历：（LeetCode 144）
         *  1.2.2 非递归的中序遍历：（LeetCode 94）
         *  1.2.3 非递归的后序遍历：（LeetCode 145）
     *  1.3 层序遍历：（LeetCode 102、103、107）
 *  2 树的前中后层序遍历
 *   *  2.1 前序遍历：（LeetCode 589）
     *  2.2 中序遍历：
     *  2.3 后序遍历：（LeetCode 590）
     *  2.4 层序遍历：（LeetCode 429）

# 1. 二叉树的前中后序遍历（递归，非递归）以及层序遍历 #

## 1.1 二叉树前中后遍历的递归解法 ##

树的前中后序的遍历这个是很常见的问题，其递归做法相对简单，这里直接贴代码：

// 前序遍历
        public static void preorder(TreeNode treeNode) { 
            if (treeNode == null) return;
            System.out.print(treeNode.val + " ");
            preorder(treeNode.left);
            preorder(treeNode.right);
        }
        
        // 中序遍历
        public static void inorder(TreeNode treeNode) { 
            if (treeNode == null) return;
            inorder(treeNode.left);
            System.out.print(treeNode.val + " ");
            inorder(treeNode.right);
        }
    
        // 后序遍历
        public static void postorder(TreeNode treeNode) { 
            if (treeNode == null) return;
            postorder(treeNode.left);
            postorder(treeNode.right);
            System.out.print(treeNode.val + " ");
        }

从上面的代码中可以看到，树的前中后序遍历代码结构基本相同，差距只要在**何时输出根值**，前序遍历一遍历到节点时，先输出根植，中序是遍历完左子节点，后序是最后才输出，理解起来很容易。

## 1.2 二叉树前中后遍历的非递归解法 ##

接下来我们来看看如何用非递归的方式，实现前中后序遍历：

### 1.2.1 非递归的前序遍历：（LeetCode 144） ###

![在这里插入图片描述][20181213234043341.png]  
前序遍历：34、35、29、25、33、42、40、39  
根据树前序遍历的特点，我们很容易将其与栈的特点相结合，这里简单附上代码：

// 前序遍历的非递归解法
        public List<Integer> preorderTraversal(TreeNode root) { 
            List<Integer> lists = new ArrayList<>();
            if (root == null) return lists;
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
            TreeNode temp = null;
            while (!stack.isEmpty()) { 
                temp = stack.pop();
                lists.add(temp.val);
                // 这里注意，要先压入右子节点，再压入左节点
                if (temp.right != null) { 
                    stack.push(temp.right);
                }
                if (temp.left != null) { 
                    stack.push(temp.left);
                }
            }
            return lists;
        }

### 1.2.2 非递归的中序遍历：（LeetCode 94） ###

![在这里插入图片描述][20181213234043341.png]  
中序遍历：25、29、35、33、34、40、42、39  
这个实现的思路，是按照中序遍历的过程：先找到`最左的子树`，然后返回其`父节点`，然后遍历`右子树`，这个返回的动作可以让我们联想到使用栈这个数据结构，实现代码：

// 二叉树非递归的中序遍历
        public List<Integer> inorderTraversal(TreeNode root) { 
        	if (root == null) { 
        		return new ArrayList<>();
        	}
            Stack<TreeNode> stack = new Stack<>();
            TreeNode node = root, temp = null;
            List<Integer> lists = new ArrayList<>();
            
            // 判断条件：所有栈为空，且节点指向为空，即所有节点已经完成遍历
            while (!stack.isEmpty() || node != null) { 
                // 向左搜索，寻找最左的节点，即中序遍历的第一个节点
                while (node != null) { 
                    stack.add(node);
                    node = node.left;
                }
                // 对每一个节点进行判断
                if (!stack.empty()) { 
                    // 获取当前节点
                    temp = stack.pop();
                    // 遍历该节点
                    lists.add(temp.val);
                    // 如果该节点为内部节点，则按中序遍历的顺序，遍历其右子节点
                    node = temp.right;
                }
            }
            return lists;
        }

### 1.2.3 非递归的后序遍历：（LeetCode 145） ###

非递归的后序遍历比较麻烦，但如果我们发现以下规律，就会变得简单：  
例如：  
![在这里插入图片描述][20181213234043341.png]  
对于后序遍历，结果：25、29、33、35、40、39、42、34  
后序遍历的方法，就是先左子树，后右子树，再最后根节点，如果反过来，顺序就变成了：先根节点，后右子树，再左子树，是不是跟先序遍历有点像呢？就是先序遍历根节点遍历之后，下一个是遍历左子树，而下一个再遍历右子树。我们按这种反过来的顺序进行遍历，结果：34、42、39、40、35、33、29、25。很容易发现跟上面后序遍历的结果刚好相反。  
因此，后序遍历可以变为：**先遍历根节点，后遍历右子树，再遍历左子树，的结果的逆序**，我们修改先序遍历的代码，可以得到：

public List<Integer> postorderTraversal_(TreeNode root) { 
            LinkedList<Integer> lists = new LinkedList<>();
            if (root == null) return lists;
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
            TreeNode temp = null;
            while (!stack.isEmpty()) { 
                temp = stack.pop();
                lists.addFirst(temp.val);
                if (temp.left != null) { 
                    stack.push(temp.left);
                }
                if (temp.right != null) { 
                    stack.push(temp.right);
                }
            }
            return lists;
        }

这里使用了LinkedList，目的是为了让我们每一次插入结果，都可以插入到当前结果的最前面，相当于实现逆序的过程。

## 1.3 层序遍历：（LeetCode 102、103、107） ##

层序遍历，就是按照每一层的顺序，一层一层的访问，例如：  
![在这里插入图片描述][20181213234614546.png]  
层序遍历的结果为：\[\[34\], \[35, 42\], \[29, 33, 40, 39\], \[25\]\]

// 根据层序遍历的特点，我们很容易想到使用队列，利用广度优先遍历的方式，进行遍历
        public List<List<Integer>> levelOrder(TreeNode root) { 
            if (root == null) { 
                return new ArrayList<>();
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            List<List<Integer>> lists = new ArrayList<>();
            List<Integer> arrays = new ArrayList<>();
            TreeNode temp = null;
            while (!queue.isEmpty()) { 
                int n = queue.size();
                // 这里通过读取队列的元素，获取这一层有多少个元素
                for (int i = 0; i < n; i++) { 
                    temp = queue.poll();
                    arrays.add(temp.val);
                    if (temp.left != null) { 
                        queue.add(temp.left);
                    }
                    if (temp.right != null) { 
                        queue.add(temp.right);
                    }
                }
                // 将每一层的数据放入到链表中
                lists.add(new ArrayList<>(arrays));
                arrays.clear();
            }
            return lists;
        }

# 2 树的前中后层序遍历 #

上面讲的都是二叉树，那对于一棵普通的树，其前中后序遍历，是如何呢：

## 2.1 前序遍历：（LeetCode 589） ##

// 递归实现
    	public List<Integer> preorder(Node root) { 
            List<Integer> result = new ArrayList<>();
            if (root == null) { 
                return result;
            }
            helper(result, root);
            return result;
        }
    
        private void helper(List<Integer> list, Node root) { 
            list.add(root.val);
            for (Node node: root.children
                 ) { 
                helper(list, node);
            }
        }
        
        // 非递归的N叉树前序遍历
        public List<Integer> preorder(Node root) { 
       		List<Integer> result = new ArrayList<>();
            if (root == null) { 
                return result;
            }
    
            Stack<Node> stack = new Stack<>();
            stack.add(root);
            while (!stack.isEmpty()) { 
                Node temp = stack.pop();
                result.add(temp.val);
    			// 注意这里要入栈的顺序是从右边最后一个子树开始
                for (int i = temp.children.size() - 1; i >= 0; i--) { 
                    stack.add(temp.children.get(i));
                }
            }
    
            return result;

## 2.2 中序遍历： ##

发现 LeetCode 没有N叉树的中序遍历，关于中序遍历，我们要注意：先遍历最左的一个子树，然后根节点，然后才是遍历其他子节点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70]  
遍历结果：5、3、6、1、2、4

## 2.3 后序遍历：（LeetCode 590） ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70]  
后序遍历：5、6、3、2、4、1  
规律：遍历每个节点，先遍历节点的子节点，最后输入根节点。  
这里可以参考二叉树的后序遍历，也使用逆转考虑的方法，先遍历根节点，然后按逆序访问孩子节点，最后将结果进行逆序处理。

// 递归实现：
        public List<Integer> postorder(Node root) { 
            List<Integer> result = new ArrayList<>();
            if (root == null) { 
                return result;
            }
            helper(result, root);
            return result;
        }
    
        private void helper(List<Integer> list, Node root) { 
            for (Node node : root.children
            ) { 
                helper(list, node);
            }
            list.add(root.val);
        }
    
    	// 非递归：
    	public List<Integer> postorder(Node root) { 
            List<Integer> list = new ArrayList<>();
            if (root == null) return list;
            
    		Stack<Node> stack = new Stack<>();
            stack.add(root);
            while (!stack.isEmpty()) { 
                Node temp = stack.pop();
                result.add(temp.val);
                stack.addAll(temp.children);
            }
            // 将结果进行逆序
            Collections.reverse(list);
            return list;
        }

## 2.4 层序遍历：（LeetCode 429） ##

// N叉树的层序遍历
        public List<List<Integer>> levelOrder(Node root) { 
            List<List<Integer>> lists = new ArrayList<>();
            if (root == null) { 
            	return lists;
            }
            
            Queue<Node> queue = new LinkedList<>();
            queue.add(root);
            List<Integer> list = new ArrayList<>();
            Node temp = null;
            while (!queue.isEmpty()) { 
                int levelSize = queue.size();
                for (int i = 0; i < levelSize; i++) { 
                    temp = queue.poll();
                    // 跟二叉树的层序遍历的区别在于，这里加入的是所有子树
                    queue.addAll(temp.children);
                    list.add(temp.val);
                }
                lists.add(new ArrayList<>(list));
                list.clear();
            }
            
            return lists;
        }

[20181213234043341.png]: /images/20210920/8ca223b5fe624352b3499729747ec127.png
[20181213234614546.png]: /images/20210920/38145d521834423cb5c1b95a9433f5a8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70]: /images/20210920/4fb7e096a40d4339be4fb2950c8d5df8.png