Java, clean, no helper, recursive


  • 8
    public class Solution {
        public int sumOfLeftLeaves(TreeNode n) {
            if(n==null ||(n.left==null && n.right ==null))return 0;
            int l=0,r=0;
            if(n.left!=null)l=(n.left.left==null && n.left.right==null)?n.left.val:sumOfLeftLeaves(n.left);
            if(n.right!=null)r=sumOfLeftLeaves(n.right);
            return l+r;
        }
    }
    

  • 1
    P

    Great solution.. Made it more simpler.. Checking n.right for null can be avoided..

        public int sumOfLeftLeaves(TreeNode n) {
            if(n==null ||(n.left==null && n.right ==null))  return 0;
            int l=0;
            if(n.left!=null)l=(n.left.left==null && n.left.right==null)?n.left.val:sumOfLeftLeaves(n.left);
            return l+sumOfLeftLeaves(n.right);
        }
    

  • 1
    S

    Simplified version:

        public int sumOfLeftLeaves(TreeNode root) {
            if (root == null) return 0;
            int l = 0;
            if (root.left != null) l = root.left.left == null && root.left.right == null ? root.left.val : sumOfLeftLeaves(root.left);
            return l + sumOfLeftLeaves(root.right);
        }
    

  • 2
    public class Solution {
        public int sumOfLeftLeaves(TreeNode root) {
            if (root == null) return 0;
    
            if (root.left != null && (root.left.left == null && root.left.right == null)) {
                return sumOfLeftLeaves(root.right) + root.left.val;
            }
    
            return  sumOfLeftLeaves(root.right) + sumOfLeftLeaves(root.left);
        }
    }
    

  • 0
    S

    @liupangzi Hi I also came up with the same idea. My initial thought was to use divide and conquer to solve this problem. When I finished my solution, I realized that it is not a standard divide and conquer format, since it might also goes into the recursion in "return sumOfLeftLeaves(root.right) + root.left.val;".

    So now I'm confused about the time complexity of this solution. Since the format is not standard, I think I might can't use Master Theorem to analyze the run time.

    Can you give me some hints about the run time? Thank you very much!


  • 1

    @Sparrow_M

    the time complexity is O(n), since for any node TreeNode root of the tree, we may only check once:

    1. if the condition is root == null, return;
    2. if the condition is root.left != null && (root.left.left == null && root.left.right == null)(we don't even need to care what is means when we analyse the time complexity), we check the right child;
    3. Or, we check both left child and right child.

  • 0
    S

    @liupangzi
    Oh yes you're right! Don't really need to trying to fit in the master theroem equation... Can just analyze by classifying all possible ways! Thank you very much :)


Log in to reply
 

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