*Java* Not the best, only a solution to consider (HashSet + Stack)


  • 0
    E

    I used a hashset to store the visited nodes, so it is not as efficient as those using stack only. The idea is to mimic graph DFS.

    public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
    	List<Integer> list = new ArrayList<Integer>();
    	if(root==null) return list;
    	
    	HashSet<TreeNode> set = new HashSet<TreeNode>();
    	Stack<TreeNode> stack = new Stack<TreeNode>();
    	stack.push(root);
    	set.add(root);
    	while(!stack.isEmpty()) {
    		TreeNode current = stack.peek();
    		if(current.left!=null && !set.contains(current.left)) {
    			set.add(current.left);
    			stack.push(current.left);
    		}
    		else {
    			list.add(current.val);
    			stack.pop();
    			if(current.right!=null)
    				stack.push(current.right);
    		}
    	}
    	return list;
    }
    }

  • 0
    A

    I have implemented inorder traversal using HashSet which to store the visited nodes. The memory limit exceeded exception bothered me. I'd like to see your answer here to prove my previous idea is correct though it could be better.


Log in to reply
 

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