Wednesday, January 27, 2021
More

    Binary Tree Path Sum

    Must Read

    Programmerhttp://www.improgrammer.net
    We started this site to inspire young minds to motivate and encourage them towards Programming Language. In this site you will get programming tutorials, tech, programming facts, programming fun and programming blogs.

    Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

    For example:
    Given the below binary tree and sum = 12,
    5
    / \
    4 8
    /\ / \

    3
    return true, as there exist a root-to-leaf path 5->4->3 which sum is 12.


    Approach 1:

    public class Solution {
        int sum1=0;
        boolean flag;
        TreeNode root1;
        int targetsum;
        public boolean hasPathSum(TreeNode root, int sum) {
            if(root==null){
                return false;
            }
            root1=root;
            
            return checksum(root, sum);
        }
            public boolean checksum(TreeNode root, int sum) {
                if(root.val==sum && root!=null){
                    return true;
                }
                if(root.val<sum){
                  sum1=sum-root.val;
                  if(sum1==0 && root.left==null && root.right==null) 
                      return true;
                  flag = checksum(root.left,sum1); 
                  if (flag==false){
                      sum1=targetsum-root1.val;
                      flag=checksum(root.right,sum1);
                  }    
                      
                  return flag;  
                }
            return false;           
                
        }
    }

     


    Approach 2: Recursive Java (Optimal)

    public class Solution {
        public boolean hasPathSum(TreeNode root, int sum) {
            if(root == null) return false;
        
            if(root.left == null && root.right == null && sum - root.val == 0) return true;
        
            return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
        }
    }

    Approach 3: Using Post Order Traversal

    In the postorder traversal, the node will be removed from the stack only when the right sub-tree has been visited. so the path will be stored in the stack. we can keep check the SUM, the length from root to leaf node.
    at leaf node, if SUM == sum, OK, return true. After postorder traversal, return false.

    I have compared this solution with recursion solutions. In the leetcode OJ, the run time of two solutions is very near.

    below is my iterator code.

    class Solution {
    public:
        bool hasPathSum(TreeNode *root, int sum) {
            stack<TreeNode *> s;
            TreeNode *pre = NULL, *cur = root;
            int SUM = 0;
            while (cur || !s.empty()) {
                while (cur) {
                    s.push(cur);
                    SUM += cur->val;
                    cur = cur->left;
                }
                cur = s.top();
                if (cur->left == NULL && cur->right == NULL && SUM == sum) {
                    return true;
                }
                if (cur->right && pre != cur->right) {
                    cur = cur->right;
                } else {
                    pre = cur;
                    s.pop();
                    SUM -= cur->val;
                    cur = NULL;
                }
            }
            return false;
        }
    };

     

     

    Latest Articles

    More Recipes Like This