二叉树的前中后序遍历-蒲公英云

作者：渴望力量的土狗

博客主页：渴望力量的土狗的博客主页

专栏：手把手带你刷牛客

工欲善其事必先利其器，给大家介绍一款超牛的斩获大厂offer利器——牛客网

点击免费注册和我一起刷题吧

二叉树的前序遍历：

一、解题思路：递归

二、解题思路：迭代

二叉树的中序遍历：

一、解题思路：递归

二、解题思路：迭代

二叉树的后序遍历：

一、解题思路：递归

二、解题思路：迭代

二叉树的前序遍历：

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

如图所示：

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

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

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

示例 1：

输入：
{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：

输入：
{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 ，树的各节点的值各不相同

输入：
{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;
    }
}