Simple Stack Solution


  • 0
        public int sumNumbers(TreeNode root) {
    		if(root==null) return 0;
    		if(root.left==null && root.right==null) return root.val;
    		Stack<TreeNode> tovisit = new Stack<TreeNode>();
    		Stack<Integer> values = new Stack<Integer>();
    		tovisit.push(root);
    		values.push(root.val);
    		int sum = 0;
    		while(!tovisit.empty()) {
    			TreeNode visiting = tovisit.pop();
    			int currVal = values.pop();
    			if(visiting.left==null && visiting.right==null) sum+=currVal;
    			else {
    				if(visiting.left!=null) {
    					tovisit.push(visiting.left);
    					values.push(currVal*10+visiting.left.val);
    				}
    				if(visiting.right!=null) {
    					tovisit.push(visiting.right);
    					values.push(currVal*10+visiting.right.val);
    				}
    			}
    		}
    		return sum;
    	}
    
    • Depth-first search using stack, and a second stack to keep the value
      at a given node.
    • It would be possible to avoid using a second stack by modifying the
      values in the children nodes (by setting the value of the children at
      (currVal*10+child.val).
    • I prefer not to modify the input tree as if we are in a real problem
      could be useful to keep the original tree.

Log in to reply
 

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