2 ms Java Solution with Inline Explanation


  • 2
    S
    public class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            // initialize result
            List<Integer> result = new LinkedList<Integer>();
            // if empty input, return empty result
            if (root == null) {
                return result;
            }
            // create assited structures
            LinkedList<TreeNode> stack = new LinkedList<TreeNode>();    // stack to cache tree node
            HashSet<TreeNode> visited = new HashSet<TreeNode>();        // visited hash enables back tracing
            // initiate by pushing the root to the stack
            stack.push(root);
            while (!stack.isEmpty()) {
                // IMPORTANT! peek the node first
                TreeNode node = stack.peek();
                // if the node has unvisited left child, push left and continue
                if (node.left != null && !visited.contains(node.left)) {
                    stack.push(node.left);
                    continue;
                }
                // reach here means no unvisited left child, safe to pop the node and add to the result
                node = stack.pop();
                result.add(node.val);
                visited.add(node);
                // push the right node to stack
                if (node.right != null && !visited.contains(node.right)) {
                    stack.push(node.right);
                }
            }
            // return result
            return result;
        }
    }

  • 0
    Y
        if (node.right != null && !visited.contains(node.right)) {
                stack.push(node.right);
            }
    

    can be changed to
    if (node.right != null) {
    stack.push(node.right);
    }


Log in to reply
 

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