二叉树的前中后序遍历

小咪咪 2024-04-03 10:05 45阅读 0赞

![ced485cbb11e458d81a746890b32cf3f.gif][]

> 作者：渴望力量的土狗
> 
> 博客主页：[渴望力量的土狗的博客主页][Link 1]
> 
> 专栏：[手把手带你刷牛客][Link 2]
> 
> 工欲善其事必先利其器，给大家介绍一款超牛的斩获大厂offer利器——牛客网
> 
> [点击免费注册和我一起刷题吧][Link 3]

![d28543928b544e3db18cf98151ce783f.png][]

**目录**

二叉树的前序遍历：

一、解题思路：递归

二、解题思路：迭代

二叉树的中序遍历 ：

一、解题思路：递归

二、解题思路：迭代

二叉树的后序遍历 ：

一、解题思路：递归

二、解题思路：迭代

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

## 二叉树的前序遍历： ##

[二叉树][Link 4]的前序遍历的记忆法则是“根左右"，即先遍历根节点，再遍历左子树节点，再遍历右子树节点。

如图所示：![3f6957d485721213ec35be97bbe89d42.png][]

其遍历结果为【A, B, D, E, C, F, G】

给你二叉树的根节点 root ，返回它节点值的 前序遍历。

数据范围：二叉树的节点数量满足1≤n≤100 ，二叉树节点的值满足1≤val≤100，树的各节点的值各不相同

示例 1：

![f005cf2b0b2f4deaba740359028e77a4.png][]

输入：
    {1,#,2,3}
    返回值：
    [1,2,3]

### 一、解题思路：递归 ###

public class Solution {
    
        List<Integer> list = new ArrayList<>();
    
        public int[] preorderTraversal (TreeNode root) {
            List<Integer> list = preOrder(root);
            int[] res = new int[list.size()];
            for (int i = 0; i < list.size(); i++) {
                res[i] = list.get(i);
            }
            return res;
        }
    
        List<Integer> preOrder(TreeNode node) {
            if (node == null) {
                return list;
            }
            list.add(node.val);
            preOrder(node.left);
            preOrder(node.right);
            return list;
        }
    }

### 二、解题思路：迭代 ###

import java.util.*;
    
    /*
     * public class TreeNode {
     *   int val = 0;
     *   TreeNode left = null;
     *   TreeNode right = null;
     *   public TreeNode(int val) {
     *     this.val = val;
     *   }
     * }
     */
    
    public class Solution {
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         * 
         * @param root TreeNode类 
         * @return int整型一维数组
         */
        public int[] preorderTraversal (TreeNode root) {
            // 结果集合
            ArrayList<Integer> arr = new ArrayList();
            if(root == null) {
                return new int[0];
            }
            TreeNode current;
            // LinkedList 当作栈来使用
            LinkedList<TreeNode> list = new LinkedList<TreeNode>();
            list.addFirst(root);
            while(!list.isEmpty()) {
                current = list.removeFirst();
                arr.add(current.val);
                if(current.right != null) {
                    list.addFirst(current.right);
                }
                if(current.left != null) {
                    list.addFirst(current.left);
                }
            }
            // 循环赋值。
            int[] res = new int[arr.size()];
            for(int i = 0; i < arr.size(); i++) {
                res[i] = arr.get(i);
            }
            return res;
        }
    }

## 二叉树的中序遍历 ： ##

中序遍历是 二叉树遍历 的一种，也叫做 中根遍历 、中序周游。 在二叉树中，中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。

给定一个二叉树的根节点root，返回它的中序遍历结果。

数据范围：树上节点数满足10000≤n≤1000，树上每个节点的值满足 −1000≤val≤1000  
进阶：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)

示例1：

![94518b5e352646f0ae081d7aecf13439.png][]

输入：
    {1,2,#,#,3}
    返回值：
    [2,3,1]

### 一、解题思路：递归 ###

import java.util.*;
    public class Solution {
        public void inorder(List<Integer> list, TreeNode root){
            //遇到空节点则返回
            if(root == null) 
                return;
            //先去左子树
            inorder(list, root.left); 
            //再访问根节点
            list.add(root.val); 
            //最后去右子树
            inorder(list, root.right); 
        }
        
        public int[] inorderTraversal (TreeNode root) {
            //添加遍历结果的数组
            List<Integer> list = new ArrayList(); 
            //递归中序遍历
            inorder(list, root); 
            //返回的结果
            int[] res = new int[list.size()]; 
            for(int i = 0; i < list.size(); i++)
                res[i] = list.get(i);
            return res;
        }
    }

### 二、解题思路：迭代 ###

import java.util.*;
    public class Solution {
        public int[] inorderTraversal (TreeNode root) {
            //添加遍历结果的数组
            List<Integer> list = new ArrayList(); 
            Stack<TreeNode> s = new Stack<TreeNode>();
            //空树返回空数组
            if(root == null) 
                return new int[0];
            //当树节点不为空或栈中有节点时
            while(root != null || !s.isEmpty()){ 
                //每次找到最左节点
                while(root != null){ 
                    s.push(root);
                    root = root.left;
                }
                //访问该节点
                TreeNode node = s.pop(); 
                list.add(node.val); 
                //进入右节点
                root = node.right; 
            }
            //返回的结果
            int[] res = new int[list.size()]; 
            for(int i = 0; i < list.size(); i++)
                res[i] = list.get(i);
            return res;
        }
    }

## 二叉树的后序遍历 ： ##

后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点

给定一个二叉树，返回他的后序遍历的序列。

后序遍历是值按照 左节点->右节点->根节点 的顺序的遍历。

数据范围：二叉树的节点数量满足 1≤n≤100 ，二叉树节点的值满足1≤val≤100 ，树的各节点的值各不相同

![d10eadcc51874294bb711dca329bad55.png][]

输入：
    {1,#,2,3}
    返回值：
    [3,2,1]

### 一、解题思路：递归 ###

import java.util.*;
    public class Solution {
        public void postorder(List<Integer> list, TreeNode root){
            //遇到空节点则返回
            if(root == null) 
                return;
            //先去左子树
            postorder(list, root.left); 
            //再去右子树
            postorder(list, root.right); 
            //最后访问根节点
            list.add(root.val); 
        }
        
        public int[] postorderTraversal (TreeNode root) {
            //添加遍历结果的数组
            List<Integer> list = new ArrayList(); 
            //递归后序遍历
            postorder(list, root); 
            //返回的结果
            int[] res = new int[list.size()]; 
            for(int i = 0; i < list.size(); i++)
                res[i] = list.get(i);
            return res;
        }
    }

### 二、解题思路：迭代 ###

import java.util.*;
    public class Solution {
        public int[] postorderTraversal (TreeNode root) {
            //添加遍历结果的数组
            List<Integer> list = new ArrayList(); 
            Stack<TreeNode> s = new Stack<TreeNode>();
            TreeNode pre = null;
            while(root != null || !s.isEmpty()){ 
                //每次先找到最左边的节点
                while(root != null){ 
                    s.push(root);
                    root = root.left;
                }
                //弹出栈顶
                TreeNode node = s.pop(); 
                //如果该元素的右边没有或是已经访问过
                if(node.right == null || node.right == pre){ 
                    //访问中间的节点
                    list.add(node.val); 
                    //且记录为访问过了
                    pre = node; 
                }else{
                    //该节点入栈
                    s.push(node); 
                    //先访问右边
                    root = node.right; 
                }
            }
            //返回的结果
            int[] res = new int[list.size()]; 
            for(int i = 0; i < list.size(); i++)
                res[i] = list.get(i);
            return res;
        }
    }

![0adcbb015b104b77b0f11eb310cf5335.png][]

>  “ 本期的分享就到这里了， 记得给博主一个三连哈，你的支持是我创作的最大动力！

[ced485cbb11e458d81a746890b32cf3f.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/4552146beba3407886cd3af3a53f3991.gif
[Link 1]: https://blog.csdn.net/m0_67995737?type=blog
[Link 2]: https://blog.csdn.net/m0_67995737/category_11980422.html
[Link 3]: https://www.nowcoder.com/link/pc_csdncpt_ylcxx_c
[d28543928b544e3db18cf98151ce783f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/155209c68472472caf402c31e6c7408e.png
[Link 4]: https://so.csdn.net/so/search?q=%E4%BA%8C%E5%8F%89%E6%A0%91&spm=1001.2101.3001.7020
[3f6957d485721213ec35be97bbe89d42.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/686b8fbb0efd425f984c02806df67863.png
[f005cf2b0b2f4deaba740359028e77a4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/69b5ed833d634315aa09b15d6479e718.png
[94518b5e352646f0ae081d7aecf13439.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/183ae77b164b447797e9a4a535b90062.png
[d10eadcc51874294bb711dca329bad55.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/3a465f0c69004923b906299f9e476b6d.png
[0adcbb015b104b77b0f11eb310cf5335.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/a9af460f8cef4e86b8ddd628ec3a4a65.png