Simple JAVA solution, cutting branch makes it more straightforward.

  • 5
    public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> result = new LinkedList<>();
            if (root == null) return result;
            Stack<TreeNode> stack = new Stack<TreeNode>();
            while (!stack.isEmpty()) {
                TreeNode cur = stack.pop();
                if (cur.right != null) stack.push(cur.right);
                // only add to the result when left sub tree is null
                if (cur.left == null) result.add(cur.val);
                else {
                    // if left sub tree is no null, we need to
                    // add it back to the stack, but after its left sub tree.
                    // then set the left subtree to null.(next time we can
                    // add it)
                    cur.left = null;
                    cur.right = null;// we also need to cut the right subtree.
            return result;

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.