23 binary-tree-inorder-traversal

题目描述

给出一棵二叉树，返回这棵树的中序遍历
例如：
给出的二叉树为{1,#,2,3},

1↵ ↵ 2↵ /↵ 3↵
返回[1,3,2].

备注：递归的解法太没有新意了，你能用迭代的方法来解这道题吗？

代码

思路：迭代

public ArrayList<Integer> inorderTraversal (TreeNode root) {
        // write code here
        ArrayList<Integer> arr = new ArrayList<Integer>();
        if(root==null)return arr;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        while(!stack.isEmpty()||root!=null) {
            while(root!=null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            arr.add(root.val);
            root = root.right;
        }
        return arr;
    }