Java BFS, DFS, Recursion


  • 0

    DFS (stack):

    public int sumOfLeftLeaves(TreeNode root) {
            if (root == null || (root.left == null && root.right == null)) return 0;
            Stack<TreeNode> stack = new Stack<TreeNode>();
            stack.push(root);
            TreeNode node;
            int sum = 0;
            while (!stack.empty()) {
                node = stack.pop();
                if (node.right != null) {
                    stack.push(node.right);
                }
                if (node.left != null) {
                    stack.push(node.left);
                    if (node.left.left == null && node.left.right == null) sum += node.left.val;
                }
            }
            return sum;
        }
    

    BFS (queue):

    public int sumOfLeftLeaves(TreeNode root) {
            if (root == null || (root.left == null && root.right == null)) return 0;
            int sum = 0;
            Deque<TreeNode> q = new ArrayDeque<TreeNode>();
            q.add(root);
            while (!q.isEmpty()) {
                TreeNode tmp = q.poll();
                if (tmp.left != null) {
                    q.add(tmp.left);
                    if (tmp.left.left == null && tmp.left.right == null) sum += tmp.left.val;
                }
                if (tmp.right != null) {
                    q.add(tmp.right);
                }
            }
            return sum;
        }
    

    recursion:

    public int sumOfLeftLeaves(TreeNode root) {
            if (root == null || (root.left == null && root.right == null)) return 0;
            int sum = 0;
            if (root.left != null) {
                if (root.left.left == null && root.left.right == null) sum += root.left.val;
                else sum += sumOfLeftLeaves(root.left);
            }
            if (root.right != null) sum += sumOfLeftLeaves(root.right);
            return sum;
        }
    

Log in to reply
 

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