Java solution use map


  • 0
    D

    I use a map to store the visited nodes. Though accepted, it's not that efficient.

        public List<Integer> postorderTraversal(TreeNode root) {
    	List<Integer> resultList=new ArrayList<>();
    	if(root==null)
    		return resultList;
    	Map<TreeNode,Integer> visitedMap=new HashMap<>(); //save nodes that are visited
    	Stack<TreeNode> toBeVisitedStack=new Stack<>();
    	toBeVisitedStack.push(root);
    	while(!toBeVisitedStack.isEmpty()){
    		TreeNode tempNode=toBeVisitedStack.peek(); // peek but not pop a node
    		if(tempNode.left==null && tempNode.right==null){ //if there is no left and right child,visit
    			resultList.add(tempNode.val);
    			visitedMap.put(tempNode, 1);
    			toBeVisitedStack.pop(); //pop the visited node
    			continue;
    		}else if(!((tempNode.left!=null&&visitedMap.get(tempNode.left)==null )|| (tempNode.right!=null && visitedMap.get(tempNode.right)==null)))
    		{
    			//left and right child of the node are visited, visit the node
    			resultList.add(tempNode.val);
    			toBeVisitedStack.pop();
    			visitedMap.put(tempNode, 1);
    			continue;
    		}
    		if(tempNode.left!=null){
    			while(tempNode.left!=null && visitedMap.get(tempNode.left)==null){//if left child has't been visited
    				toBeVisitedStack.push(tempNode.left);
    				tempNode=tempNode.left;
    			}
    		}
    		if(tempNode.right!=null){
    			if(visitedMap.get(tempNode.right)==null){//if right child hasn't been visited
    				toBeVisitedStack.push(tempNode.right);
    			}    			
    		}
    	}
    	return resultList;        
    }

Log in to reply
 

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