Three ways to solve by java


  • 0
    Z
    1. DFS, iteratively traverse with stack
    public class Solution {
        public int sumNumbers(TreeNode root) {
            if (root == null) {
                return 0;
            }
            
            Stack<TreeNode> stack = new Stack<TreeNode>();
            Stack<Integer> sum_stack = new Stack<Integer>();
            stack.push(root);
            sum_stack.push(root.val);
            
            int sum = 0;
            while (!stack.isEmpty()) {
                TreeNode node = stack.pop();
                Integer current = sum_stack.pop();
                
                if (node.left == null && node.right == null) {
                    sum += current;
                }
                
                if (node.left != null) {
                    stack.push(node.left);
                    sum_stack.push(current * 10 + node.left.val);
                }
                if (node.right != null) {
                    stack.push(node.right);
                    sum_stack.push(current * 10 + node.right.val);
                }
            }
            
            return sum;
        }
    }
    
    1. BFS with queue. have to change the value of node
    public class Solution {
        public int sumNumbers(TreeNode root) {
            if (root == null) {
                return 0;
            }
            
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            queue.offer(root);
            
            int sum = 0;
            while (!queue.isEmpty()) {
                TreeNode node = queue.poll();
                if (node.left == null && node.right == null) {
                    sum += node.val;
                }
                
                if (node.left != null) {
                    node.left.val += node.val * 10;
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    node.right.val += node.val * 10;
                    queue.offer(node.right);
                }
            }
            
            return sum;
        }
    }
    
    1. DFS recursively, with helper function
    public class Solution {
        
        int sum = 0;
        
        public int sumNumbers(TreeNode root) {
            if (root == null) {
                return 0;
            }
            
            helper(root, root.val);
            return sum;
        }
        
        private void helper(TreeNode root, int current) {
            if (root.left == null && root.right == null) {
                sum += current;
            }
            
            if (root.left != null) {
                helper(root.left, current * 10 + root.left.val);
            }
            if (root.right != null) {
                helper(root.right, current * 10 + root.right.val);
            }
        }
    }
    

Log in to reply
 

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