Two Stacks Simple Iterative Java Solution


  • 0
    K

    Below is my iterative solution. If you insist on preorder traversal, you can swap the order of visiting right first. Basically, you save the prev value for each child node, meanwhile save that child node into stack. When both children are null, it's time to sum.

    	public int sumNumbers(TreeNode root) {
    		if (root == null) return 0;
    		Stack<TreeNode> nodes = new Stack<>();
    		Stack<Integer> nums = new Stack<>();
    		nodes.push(root);
    		nums.push(0);
    		int sum = 0;
    		while (!nodes.isEmpty()) {
    			TreeNode cur = nodes.pop();
    			int prev = nums.pop();
    			if (cur.left == null && cur.right == null) {
    				sum += prev * 10 + cur.val;
    			} else {
    				if (cur.left != null) {
    					nodes.push(cur.left);
    					nums.push(prev * 10 + cur.val);
    				}
    				if (cur.right != null) {
    					nodes.push(cur.right);
    					nums.push(prev * 10 + cur.val);
    				}
    			}
    		}
    		return sum;
    	}
    

Log in to reply
 

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