Leetcode 二叉树的中序遍历

题目：二叉树的中序遍历
难度：中等

直接根据中序遍历的关系，放入到对应的list当中即可，不难

主要用的是迭代 然后递归的方法实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res=new ArrayList<Integer>();
        inorder(root,res);
        return res;


    }

    public void inorder(TreeNode root,List<Integer> res){
        if(root==null){
            return;
        }
        inorder(root.left,res);
        res.add(root.val);
        inorder(root.right,res);
    }
}

很明显，每个节点都会被遍历到，那么空间复杂度就是O(n)

第二种方法：则是使用堆栈的方式，首先将整个树向左子树遍历一遍，直到没有左子树，就pop出来并放入list当中，循环操作，直至把root遍历完

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res=new ArrayList<Integer>();
        Deque<TreeNode> stk=new LinkedList<TreeNode>();
        while(root!=null||!stk.isEmpty()){
            while(root!=null){
                stk.push(root);
                root=root.left;
            }
            root=stk.pop();
            res.add(root.val);
            root=root.right;
        }
        return res;


    }


}

时间复杂度仍然是O（n），因为都是遍历了一遍