LeetCode 二叉树的前序/中序/后序遍历-一一网

这是我参与更文挑战的第 20 天，活动详情查看：更文挑战

二叉树的前序遍历（144）

题目描述

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

示例 1：

输入：root = [1,null,2,3]
输出：[1,2,3]
复制代码

示例 2：

输入：root = []
输出：[]
复制代码

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

**进阶：**递归算法很简单，你可以通过迭代算法完成吗？

思路分析

递归的方法很简单，所以我们重点介绍一下迭代方式，递归会隐式的为我们模拟一个栈，我们使用迭代的方式，我们可以显示的建一个栈，然后通过两个while 循环去遍历，后序遍历的方式和前序遍历的方式可以通过一定的转换，后面我们再讲后续遍历的时候会讲到，我们使用的也是这种方式，通过这种方式，一下子就记住了两种遍历方式。

代码展示

解法一：时间复杂度是 ${O(n)}$ ，空间复杂度是 ${O(n)}$ 。

public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> rootList = new ArrayList<>();
        preoderInternal(root,rootList);
        return rootList;
    }

    private void preoderInternal(TreeNode root,List<Integer> list){
        if(root == null){
            return;
        }
        list.add(root.val);
        preoderInternal(root.left,list);
        preoderInternal(root.right,list);
    }
复制代码

解法二：时间复杂度是 ${O(n)}$ ，空间复杂度是 ${O(n)}$ 。

public List<Integer> preorderTraversal(TreeNode root) { 
        List<Integer> rootList = new ArrayList<>();
        if(root == null){
            return rootList;
        }
        Stack<TreeNode> stack = new Stack<>();
        // TreeNode node = root;
        while(root != null || !stack.isEmpty()){
            while(root != null){
                rootList.add(root.val);
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            root = root.right;

        }
        return rootList;
    }
复制代码

中序遍历

左-根-右

中序遍历和前序遍历也很像，一个是根-左-右，一个是左-根-右，所以在用栈的实现时也比较类似。

解法一：时间复杂度是 ${O(n)}$ ，空间复杂度是 ${O(n)}$ 。

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorderInternal(root,res);
        return res;

    }
    private void inorderInternal(TreeNode node,List<Integer> list){
        if(node == null){
            return;
        }
        inorderInternal(node.left,list);
        list.add(node.val);
        inorderInternal(node.right,list);
    }
复制代码

解法二：时间复杂度是 ${O(n)}$ ，空间复杂度是 ${O(n)}$ 。

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        while(root != null || !stack.isEmpty()){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }
复制代码

后序遍历

左-右-根

前序遍历是根-左-右，后序遍历是左-右-根

1：我们将前序遍历中节点插入结果链表尾部的逻辑，修改为将节点插入结果链表的头部

那么结果链表就变为了：右 -> 左 -> 根

2：我们将遍历的顺序由从左到右修改为从右到左（也就是根-左-右变成根-右-左），配合如果1

那么结果链表就变为了：左 -> 右 -> 根，这刚好是后序遍历的顺序

基于这两个思路，我们可以这么处理：修改前序遍历代码中，节点写入结果链表的代码，将插入队尾修改为插入队首；
修改前序遍历代码中，每次先查看左节点再查看右节点的逻辑，变为先查看右节点再查看左节点

解法一：

public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postorderInternal(root,res);
        return res;
    }

    private void postorderInternal(TreeNode root,List<Integer> list){
        if(root == null){
            return;
        }
        postorderInternal(root.left,list);
        postorderInternal(root.right,list);
        list.add(root.val);
    }
复制代码

解法二：

// 修改前序遍历代码中，节点写入结果链表的代码，将插入队尾修改为插入队首
// 修改前序遍历代码中，每次先查看左节点再查看右节点的逻辑，变为先查看右节点再查看左节点
    public List<Integer> postorderTraversal(TreeNode root) {  
        List<Integer> res = new ArrayList<>();
        if(res == null){
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        while(root != null || !stack.isEmpty()){

            while(root != null){
                res.add(0,root.val);
                stack.push(root);
                root = root.right;
            }
            root = stack.pop();
            root = root.left;
            
        }
        return res;

    }  
复制代码