Java non-recursive in order traversal solution


  • 0
    S
    public int sumNumbers(TreeNode root) {
    	if(root == null) return 0;
    	if(root.left == null && root.right == null) return root.val;
    	
    	int sum = 0;    	
    	Stack<TreeNode> unvisited = new Stack<TreeNode>();
    	Set<TreeNode> dup = new HashSet<TreeNode>(); 
    	TreeNode current = root;
    
    	while(!unvisited.isEmpty() || current!=null){
    		while(current!=null){
    			unvisited.push(current);
    			current = current.left;
    		}  		
    		current = unvisited.peek();
    		/* Check if current node has been visited. */
    		if(dup.contains(current)){
    			unvisited.pop();
    			current = null;
    		}
    		/* Check if current node is a leaf, if so calculate the sum. */
    		else if(current.right== null && current.left== null){
    			int d = 0;
    			int factor = 1;
    			for(int i = unvisited.size()-1; i>=0; i--){
    				d += unvisited.get(i).val*factor;
    				factor = factor*10;
    			}
    			sum += d;
    			unvisited.pop();
    			current = current.right;
    		}    				
    		else{
    			dup.add(current);
    			current = current.right;
    		}   		
    	}
    	return sum;
    }

Log in to reply
 

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