Java O(n) Easy To Understand, Optimal Solution


  • 0
    B

    Explanation
    The idea to this question is to recursively visit each of root's children, if they exist, while decrementing sum. Why we decrement sum is because we know the current root-to-leaf-path contains the value root.val, so we check if either of root's children contain a root-to-leaf-path of sum - root.val.

    Tiem Complexity
    The time complexity is O(n) where n is the size of the tree root, since we may visit each node in our tree root recursively.

    class Solution {
        public boolean hasPathSum(TreeNode root, int sum) {
            if (root == null) {
                return false;
            } 
            // Leaf node, check if root.val == sum
            else if (root.left == null && root.right == null) {
                return root.val == sum;
            } 
            // At least one child is non-null, return their pathSum results
            else {
                return hasPathSum(root.left, sum - root.val) || 
                       hasPathSum(root.right, sum - root.val);
            }
        }
    }
    

Log in to reply
 

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