Recursive and Iterative (with Hash) Solution


  • 2

    Recursive Solution is straightforward:

        public List<Integer> inorderTraversal(TreeNode root) {
    		List<Integer> inorder = new LinkedList<Integer>();
    		inorderHelper(root,inorder);
    		return inorder;
    	}
    	public void inorderHelper(TreeNode root, List<Integer> inorder) {
    		if(root==null) return;
    		inorderHelper(root.left,inorder);
    		inorder.add(root.val);
    		inorderHelper(root.right,inorder);
    	}
    

    I use an helper function and pass the result List as parameter so I don't have to create a new object List at each recursive call and then use the addAll() method on the return value;

    For the Iterative version we cannot add the elements as soon as we find them, first we need to visit them to push the children in inorder way in the stack, the second time we encounter a node we add it to the resulting list, it means we have already added all the left subtree for this node. I use an HashSet to remember the nodes already visited the first time:

        public List<Integer> inorderTraversal(TreeNode root) {
    		List<Integer> inorder = new ArrayList<Integer>();
    		if(root==null) return inorder;
    		Stack<TreeNode> tovisit = new Stack<TreeNode>();
    		Set<TreeNode> visited = new HashSet<TreeNode>();
    		tovisit.push(root);
    		while(!tovisit.empty()) {
    			TreeNode visiting = tovisit.pop();
    			if(visiting.right!=null && !visited.contains(visiting)) tovisit.push(visiting.right);
    			if(!visited.contains(visiting)) tovisit.push(visiting);
    			else inorder.add(visiting.val);
    			if(visiting.left!=null && !visited.contains(visiting)) tovisit.push(visiting.left);
    			if(!visited.contains(visiting)) visited.add(visiting);
    		}
    		return inorder;
    	}

  • 0
    R
    public class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
         List<Integer> result = new LinkedList<Integer>();
         recursiveInOrder(result,root);
         return result;
        }
        
        
    private List<Integer> recursiveInOrder(List<Integer> inOrderNodes ,TreeNode root) {
    
               if(root==null){
                    return inOrderNodes;
                }
    
               if(root.left!=null){
                    recursiveInOrder(inOrderNodes,root.left);
                }
    
                inOrderNodes.add(root.val);
    
                if(root.right!=null){
                    recursiveInOrder(inOrderNodes,root.right);
                }
                return inOrderNodes;
            }
        
    }

Log in to reply
 

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