二叉树的中序遍历

递归写法

 public int[] inorderTraversal (TreeNode root) {
        // write code here
        List<Integer> list=new ArrayList<Integer>();
        dfs(list,root);
        int[] res=new int[list.size()];
        for(int i=0;i<list.size();i++){
            res[i]=list.get(i);
        }
        return res;
    }
    public void dfs(List<Integer> list,TreeNode root){
        if (root==null) return;
        dfs(list,root.left);
        list.add(root.val);
        dfs(list,root.right);
    }

非递归写法

p加进去，p=p.left 之后p=出栈元素，list添加p，p=p.right

public int[] inorderTraversal (TreeNode root) {
        // write code here
         List<Integer> list=new ArrayList<Integer>();
        Deque<TreeNode> stack=new LinkedList<TreeNode>();
        TreeNode p=root;
        while (p!=null||!stack.isEmpty()){
            while (p!=null){
                stack.push(p);
                p=p.left;
            }
            p=stack.pop();
            list.add(p.val);
            p=p.right;
        }

        int[] res=new int[list.size()];
        for(int i=0;i<list.size();i++){
            res[i]=list.get(i);
        }
        return res;
    }