Solution with iterative preorder traversal


  • 1
    A

    During a previous interview, they don't like my answer to a tree problem with a recursive solution. Stack overflow is a common problem in the real work environment. So I think we should prefer iterative solution to recursive ones. Or we should at least practice both.

    public class Solution {        
        public int sumNumbers(TreeNode root) {
            int sum = 0, val = 0;
            ArrayList<Integer> list = new ArrayList<Integer>();
            if(root == null) {
                return 0;
            }
            
            Stack<TreeNode> stack = new Stack<TreeNode>();
            Stack<Integer> valStack = new Stack<Integer>();
            stack.push(root);
            valStack.push(root.val);
            while(!stack.isEmpty()){
                TreeNode node = stack.pop();
                val = valStack.pop();
                if(node.right == null && node.left == null){
                    sum += val;
                }
                if(node.right != null){
                    stack.push(node.right);
                    valStack.push(val*10+node.right.val);
                }
                if(node.left != null){
                    stack.push(node.left);
                    valStack.push(val*10+node.left.val);
                }
            }
            
            return sum;
        }
    }

Log in to reply
 

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