LeetCode 129 - Sum Root to Leaf Numbers

https://leetcode.com/problems/sum-root-to-leaf-numbers/

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

Note: A leaf is a node with no children.

Example:

Input: [1,2,3]
    1
   / \
  2   3
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

Example 2:

Input: [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.

X. DFS
https://leetcode.com/problems/sum-root-to-leaf-numbers/discuss/41363/Short-Java-solution.-Recursion.

public int sumNumbers(TreeNode root) {
 return sum(root, 0);
}

public int sum(TreeNode n, int s){
 if (n == null) return 0;
 if (n.right == null && n.left == null) return s*10 + n.val;
 return sum(n.left, s*10 + n.val) + sum(n.right, s*10 + n.val);
}

https://leetcode.com/problems/sum-root-to-leaf-numbers/discuss/41513/Super-simple-DFS-Solution

    public int sumNumbers(TreeNode root) {
        return sumNumbers(root, 0);
    }
    
    private int sumNumbers(TreeNode root, int sum){
        if(root == null) return 0;
        if(root.left == null && root.right == null)
            return sum + root.val;
        
        return sumNumbers(root.left, (sum + root.val) * 10) + sumNumbers(root.right, (sum + root.val) * 10);
        
    }

https://leetcode.com/problems/sum-root-to-leaf-numbers/discuss/41400/Can-you-improve-this-algorithm
- A little bit verbose

    public int sumNumbers(TreeNode root) {
        if (root == null)
            return 0;
        return sumR(root, 0);
    }
    public int sumR(TreeNode root, int x) {
        if (root.right == null && root.left == null)
            return 10 * x + root.val;
        int val = 0;
        if (root.left != null)
            val += sumR(root.left, 10 * x + root.val);
        if (root.right != null)
            val += sumR(root.right, 10 * x + root.val);
        return val;
    }

X. BFS
https://blog.csdn.net/happyaaaaaaaaaaa/article/details/51586542

以 bfs 为基础，用队列实现层次遍历。用两个队列，一个存放节点，一个存放整数和

    public int sumNumbers(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        Queue<Integer> queue1 = new LinkedList<Integer>();
        if(root == null) return 0;
        int res = 0;
        queue.add(root);
        queue1.add(0);
        while(!queue.isEmpty()) {
            int size = queue.size();
            while(size-- > 0) {
                root = queue.poll();
                int val = queue1.poll() * 10 + root.val;
                if(root.left == null && root.right == null)
                    res += val;
                if(root.left != null) {
                    queue.add(root.left);
                    queue1.add(val);
                }
                if (root.right != null) {
                    queue.add(root.right);
                    queue1.add(val);
                }
            }
        }
        return res;
    }

X. Stack

以 dfs 为基础，用栈实现深度遍历。用两个栈，一个存放节点，另一个存放整数和，其他的形式和递归十分类似：

    public int sumNumbers(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        Stack<Integer> stack1 = new Stack<>();
        stack.add(root);
        stack1.add(0);
        int res = 0;
        while (!stack.isEmpty()) {
            root = stack.pop();
            int val = stack1.pop();
            if (root != null) {
                val = val * 10 + root.val;
                if (root.left == null && root.right == null)
                    res += val;
                stack.add(root.left);
                stack1.add(val);
                stack.add(root.right);
                stack1.add(val);
            }
        }
        return res;
    }
https://leetcode.com/problems/sum-root-to-leaf-numbers/discuss/41367/Non-recursive-preorder-
traverse-Java-solution

        public int sumNumbers(TreeNode root) {
            if(root==null){
                return 0;
            }
            int sum = 0;
            TreeNode curr;
            Stack<TreeNode> ws = new Stack<TreeNode>();
            ws.push(root);
            
            while(!ws.empty()){
                curr = ws.pop();
                
                if(curr.right!=null){
                    curr.right.val = curr.val*10+curr.right.val;
                    ws.push(curr.right);
                }
                
                if(curr.left!=null){
                    curr.left.val = curr.val*10+curr.left.val;
                    ws.push(curr.left);
                }
                
                if(curr.left==null && curr.right==null){ // leaf node
                    sum+=curr.val;
                }
            }
            return sum;
        }