Java BFS Iterative Solution


  • 0
    X

    It seems that most of solutions use recursion. Here is my BFS iterative solution.

    public class Solution {
        public int sumNumbers(TreeNode root) {
            if(root == null)    return 0;
            Queue<TreeNode> tn = new LinkedList<TreeNode>();
            Queue<Integer> nums = new LinkedList<Integer>();
            ArrayList<Integer> leaf = new ArrayList<Integer>();
            
            tn.add(root);
            nums.add(0);
            while(!tn.isEmpty()){
                TreeNode node = tn.poll();
                int pre = nums.poll();
                pre = 10*pre + node.val;
                if(node.left==null && node.right==null){
                    leaf.add(pre);
                    continue;
                }
                if(node.left != null){
                    tn.add(node.left);
                    nums.add(pre);
                }
                if(node.right != null){
                    tn.add(node.right);
                    nums.add(pre);
                }
            }
            
            int sum = 0;
            for(int i: leaf)    sum += i;
            return sum;
        }
    }

Log in to reply
 

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