Day 5, leetcode 111, 112, Minimum Depth of Binary Tree, path sum

Minimum Depth of Binary Tree

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == NULL) return 0;
        int left = minDepth(root->left) + 1;
        int right = minDepth(root->right) + 1;
        
        if (root->left == NULL) return right;
        if (root->right == NULL) return left;
        
        return min(left,right);
    }
};

solution #2 by others

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (root == NULL) return 0;  
          
        int left = minDepth(root->left) + 1;  
        int right = minDepth(root->right) + 1;  
        // 叶子节点  
        if (left == 1 || right == 1)  
            return left > right ? left : right;  
              
        return left < right ? left : right;  
    }
};

BFS

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == NULL) return 0;
        queue<TreeNode*> que;
        que.push(root);
        int level = 1;
        int size = 1;
        
        while (!que.empty()) {
            if (size == 0) {
                size = que.size();
                level++;
            }else {
                TreeNode *t = que.front();
                que.pop();
                if (t->left == NULL && t->right == NULL) return level;
                if (t->left != NULL) que.push(t->left);
                if (t->right != NULL) que.push(t->right);
                size--;
            }
        }
        
        return level;
    }
};

Path Sum

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool rec (TreeNode *root, int sum, int curSum) {
        if (root == NULL) return false;
        curSum += root->val;
        if (root->left == NULL && root->right == NULL) {
            return sum == curSum;
        }
        return rec(root->left, sum, curSum) || rec(root->right, sum, curSum);
    }

    bool hasPathSum(TreeNode *root, int sum) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        return rec(root, sum, 0);
    }
};

Solution #2 by others

/** 
 * Definition for binary tree 
 * struct TreeNode { 
 *     int val; 
 *     TreeNode *left; 
 *     TreeNode *right; 
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 
 * }; 
 */  
class Solution {  
public:  
    bool hasPathSum(TreeNode *root, int sum) {  
        // Start typing your C/C++ solution below  
        // DO NOT write int main() function  
        if (root == NULL)  
        {  
            return false;  
        }  
          
        int leftsum = sum - root->val;  
        // 找到sum，并且为叶子节点  
        if (leftsum == 0 && root->left == NULL && root->right == NULL)  
        {  
            return true;  
        }  
        bool left = hasPathSum(root->left, leftsum);  
        bool right = hasPathSum(root->right, leftsum);  
  
        return left || right;  
    }  
};