No stack no resursive java solution


  • 0
    B

    credit to
    http://stackoverflow.com/questions/791052/iterating-over-a-binary-tree-with-o1-auxiliary-space

    The aim is to use extra space O(1) (not including the returning result, which worst case is O(N))

    List<List<Integer>> pathSumResult;
        public List<List<Integer>> pathSum(TreeNode root, int sum) 
        {
    		pathSumResult=new ArrayList<List<Integer>>();
    		java.util.Vector<Integer> lst;
    		TreeNode parent = root, right  = null, curr;
    		if(root!=null)
    			root.val=sum-root.val;
    		while (parent != null)
    		{
    			curr = parent.left;
    			if (curr != null)
    			{
    				// search for thread
    				while (curr != right && curr.right != null)
    					curr = curr.right;
    				if (curr != right)
    				{
    					//revise the children nodes' value
    					parent.left.val=parent.val-parent.left.val;
    					if(parent.right!=null && !checkAncestor(parent.right, parent))
    						parent.right.val=parent.val-parent.right.val;
    					// insert thread
    					curr.right = parent;
    					parent = parent.left;
    					continue;
    				}
    				else
    					// remove thread, left subtree of P already traversed
    					// this restores the node to original state
    					;//curr.right = null;
    			}
    			else
    			{
    				if(parent.right!=null && !checkAncestor(parent.right, parent))
    				{
    					parent.right.val=parent.val-parent.right.val;
    				}
    				else if(parent.val==0)
    				{
    					lst=new java.util.Vector<Integer>();
    					lst.add(0);
    					TreeNode print0=parent, print1;
    					while(!onRightLane(root,print0) && print0.right!=null)
    					{
    						print1=print0.right;
    						
    						while(!checkAncestor(print1, print0))
    						{
    							print1=print1.right;
    						}
    						int pos=0;
    						lst.add(0,print1.val);
    						TreeNode print2=print1.left;
    						while(print2!=print0)
    						{
    							lst.add(++pos,print2.val);
    							print2=print2.right;
    						}
    						print0=print1;
    					}
    					if(print0!=root)
    					{
    						int pos=0;
    						print1=root;
    						while(print1!=print0)
    						{
    							lst.add(pos++, print1.val);
    							print1=print1.right;
    						}
    					}
    					for(int ndx=lst.size()-1;ndx>0;ndx--)
    						lst.set(ndx, lst.get(ndx-1)-lst.get(ndx));
    					lst.set(0,sum-lst.get(0));
    					pathSumResult.add(lst);
    				}
    			}
    
    			right  = parent;
    			parent = parent.right;
    		}
    		return pathSumResult;
    	}
    	private boolean onRightLane(TreeNode root, TreeNode right)
    	{
    		while(root!=null)
    		{
    			if(root==right)
    				return true;
    			root=root.right;
    		}
    		return false;
    	}
    	private boolean checkAncestor(TreeNode high, TreeNode low)
    	{
    		if(high==null ||high.left==null)
    			return false;
    		if(high.left==low)
    		{
    			return true;
    		}
    		high=high.left;
    		while(high.right!=null)
    		{
    			high=high.right;
    			//System.out.println("testing "+high.val);
    			if(high==low)
    				return true;
    		}
    		return false;
    	}

Log in to reply
 

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