Java O(n) Easy To Understand, Optimal Solution

  • 0

    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.