Java Solution DFS in recursive way and iterative way, BFS in iterative way


  • 2
    A
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    // DFS recursive, this solution is straightly understandable.
    public class Solution {
        public int sumNumbers(TreeNode root) {
            return dfs(root, 0);
        }
        private int dfs(TreeNode root, int sum) {
            if (root == null) return 0;
            int newSum = root.val + sum * 10;
            if (root.left == null && root.right == null) return newSum;
            return dfs(root.left, newSum) + dfs(root.right, newSum);
        }
    }
    //Whatever iterative DFS or BFS, the point is to recode the sum of parent nodes so far.
    // DFS iterative
    public class Solution {
        public int sumNumbers(TreeNode root) {
            if (root == null) return 0;
            Stack<TreeNode> remain = new Stack<>();
            remain.push(root);
            int sum = 0;
            TreeNode travel = root;
            while(!remain.isEmpty()) {
                travel = remain.pop();
                if (travel.right != null) {
                    travel.right.val = travel.right.val + travel.val * 10;
                    remain.push(travel.right);
                }
                if (travel.left != null) {
                    travel.left.val = travel.left.val + travel.val * 10;
                    remain.push(travel.left);
                }
                if (travel.left == null && travel.right == null) {
                    sum += travel.val;
                }
            }
            return sum;
        }
    }
    // BFS iterative
    public class Solution {
        public int sumNumbers(TreeNode root) {
            if (root == null) return 0;
            int sum = 0;
            TreeNode travel = null;
            Queue<TreeNode> remain = new LinkedList<>();
            remain.offer(root);
            while(!remain.isEmpty()) {
                travel = remain.poll();
                if (travel.left != null) {
                    travel.left.val = travel.val * 10 + travel.left.val;
                    remain.offer(travel.left);
                }
                if (travel.right != null) {
                    travel.right.val = travel.val * 10 + travel.right.val;
                    remain.offer(travel.right);
                }
                if (travel.left == null && travel.right == null) sum += travel.val;
            }
            return sum;
        }
    }
    

Log in to reply
 

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