94. 二叉树的中序遍历

一、题目描述

给定一个二叉树，返回它的中序 遍历。

示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]

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

二、解题思路

  该题目旨在探讨递归与迭代的关系，递归是指在函数定义中调用函数自身的方法。递归法主要用于解决三中问题:

1. 数据的定义是按照递归定义的（Fibonacci函数）
2. 问题解法是按递归算法实现（Hanoi问题）
3. 数据的结构形式是按递归定义（二叉树）

  迭代是指重复执行一系列运算步骤，从前面的量依次求出后面的量的过程。

  一般来说，递归能解决的问题采用迭代法同样能够解决。因为递归采用了系统栈保存了任务运行状态，从而开启下一任务，当任务结束后即可恢复前一任务运行状态继续运行。迭代+栈组合亦可达到此种效果，使用栈保存迭代中运行的相关运行信息即可。

一、递归

1、解题思路

中序遍历(递归实现)

2、代码

    List<Integer> list = null;
    public List<Integer> inorderTraversal(TreeNode root) {
        list = new ArrayList<>();
        preorder(root);
        return list;
    }
    public void inorder(TreeNode root) {
        if(root != null){
            list.add(root.val);
            preorder(root.left);
            preorder(root.right);
        }
    }

二、系统栈迭代

1、解题思路

中序遍历(系统栈实现)

  模拟递归中的系统栈存储执行环境的过程；通过自定义数据结构Command存储每个命令的含义，如果message是print，则直接打印该节点的值；如果message是go，则继续遍历该节点的左右子节点。以栈的方式存储每一条命令，根据左右子节点入栈以及打印节点值的先后来进行中序遍历。

2、代码

    static class Command {
        String message;
        TreeNode node;
        Command(String message, TreeNode node) { 
            this.message = message;this.node = node;
        }
    }
    //迭代法
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer>list = new ArrayList<>();
        if(root==null)return list;
        Stack<Command>stack = new Stack<>();
        stack.push(new Command("go",root));
        while (!stack.isEmpty()){
            Command cur = stack.pop();
            if(cur.message.equals("print")){
                list.add(cur.node.val);
            }else{
                //栈 先进后出
                if(cur.node.right!=null)stack.push(new Command("go",cur.node.right));
                stack.push(new Command("print",cur.node));
                if(cur.node.left!=null)stack.push(new Command("go",cur.node.left));
            }

        }
        return list;
    }

三、栈迭代

1、解题思路

中序遍历(栈实现)

以null为标志，判定是否需要进行遍历左子树至尽头！！！

2、代码

/**
     * 以null为标志，若栈弹出的是null,则继续弹出下一个作为根节点，将其右子节点入栈
     *              若栈弹出的非null，则遍历其左子树直至入栈为null
     */
    public List<Integer> inorderTraversal1(TreeNode root) {
        List<Integer>list = new ArrayList<>·();
        if(root==null)return list;
        Stack<TreeNode>stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode cur = stack.peek();
            while (cur!=null){//遍历左子树至尽头，全部入栈(包括null)
                stack.push(cur.left);
                cur = stack.peek();
            }
            stack.pop();//空节点出栈(已遍历左子树的节点最终会入栈null，作为标志)
            if(!stack.empty()){//访问结点，向右一步
                cur = stack.pop();//(代表该节点为未遍历至尽头的节点)
                list.add(cur.val);
                if(cur!= null)stack.push(cur.right);//添加右子节点(若为null,则后续直接弹出，否则后续遍历其左子树)
            }
        }
        return list;
    }