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>();
    		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) {
    				if(visiting.right!=null) {
    		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
    • 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.