题解 | #二叉树的中序遍历#

方法一（栈）

1.题意整理

• 给定一颗二叉树。
• 按照中序打印二叉树中所有的节点。

2.思路整理

简单分析：先序遍历的顺序是根、左、右，中序遍历的顺序是左、根、右，后序遍历的顺序是左、右、根。如果直接按照递归的思路进行遍历，只需在对应的位置将当前节点加入到序列即可。

比如中序遍历：

	List<Integer> in=new ArrayList<Integer>();

	private void inorder(TreeNode root){
        if(root==null) return;
        //往左子树方向遍历
        inorder(root.left);
        //加入到序列
        in.add(root.val);
        //往右子树方向遍历
        inorder(root.right);
    }

所以，我们可以尝试使用迭代的方式来进行树的遍历。

具体思路：将根节点作为起点节点，如果当前节点不为空，不断将它以及它的左子节点入栈。如果节点为空的时候，说明是最后一个左子节点，此时逐个将栈中元素出栈，加入到in序列。由于栈是先进后出结构，所以当前顺序一定是左、根。此时需要往右子树方向遍历。

图解展示：

3.代码实现

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整型一维数组
     */
    //存储中序序列
    List<Integer> in=new ArrayList<>();
    
    public int[] inorderTraversal (TreeNode root) {
        //中序遍历
        inorder(root);
        int[] res=new int[in.size()];
        //list容器转化为数组
        for(int i=0;i<in.size();i++){
            res[i]=in.get(i);
        }
        return res;
    }
    
     //中序遍历
    private void inorder(TreeNode root){
        if(root==null) return;
        TreeNode node=root;
        //新建栈
        LinkedList<TreeNode> s=new LinkedList<>();
        while(!s.isEmpty()||node!=null){
            //如果当前节点不为空，不断将它以及它的左子节点入栈
            if(node!=null){
                s.push(node);
                node=node.left;
            }
            else{
                node=s.pop();
                //由于栈是先进后出结构，所以当前顺序一定是左、根
                in.add(node.val);
                //往右子树方向遍历
                node=node.right;
            }
        }
    }
}

4.复杂度分析

• 时间复杂度：需要遍历树中所有节点，所以时间复杂度是$O(n)O(n)$。
• 空间复杂度：需要深度不超过n的栈，所以空间复杂度为$O(n)O(n)$。