[数据结构与算法]LeetCode Easy 前26-30道

#111 Minimum Depth of Binary Tree
#112 Path Sum
#118 Pascal’s Triangle
#119 Pascal’s Triangle II
#121 Best Time to Buy and Sell Stock

#111 Minimum Depth of Binary Tree
要求：求二叉树的最浅深度
思路1：采用递归的思路，没毛病,一次AC

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(!root) return 0;
        if(!root->left && !root->right) return 1;
        int left = minDepth(root->left);
        int right = minDepth(root->right);
        int minValue = min(left,right);
        if(left == 0)
            minValue = right;
        else if(right == 0)
            minValue = left;
        return 1 + minValue;
    }
};

参考了大神博客园：Grandyang，事实证明,以后要注意代码简洁度了。

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(!root) return 0;
        if(!root->left) return 1 + minDepth(root->right);
        if(!root->right) return 1 + minDepth(root->left);
        return 1 + min(minDepth(root->left), minDepth(root->right));
    }
};

思路2：采用队列的结构，依旧是迭代，解法类似 求最大深度，只是提早进行返回了。参考题解：Maximum Depth of Binary Tree

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (!root) return 0;
        int res = 0;
        queue<TreeNode*> q{{root}};
        while (!q.empty()) {
            ++res;
            for (int i = q.size(); i > 0; --i) {
                auto t = q.front(); q.pop();
                if (!t->left && !t->right) return res;
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
            }
        }
        return -1;
    }
};

#112 Path Sum
要求：给定一个二叉树，一个值，能否找到一个路径之和等于值的，返回true
思路1：继续迭代，往下遍历即可，一次AC,注意是要到叶子节点之和的路径

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(!root) return false;
        if(root->val == targetSum && !root->left &&!root->right) return true;
        return hasPathSum(root->left, targetSum-root->val) 
            || hasPathSum(root->right,targetSum-root->val);
    } 
};

参考大神博客园：Grandyang
思路2：采用迭代的思路，一直往下求值，新起了一个节点，没想到的思路

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(!root) return false;
        stack<TreeNode*> st{{root}};
        while(!st.empty())
        {
            TreeNode* t = st.top();st.pop();
            if(!t->left && !t->right && t->val == targetSum) return true;
            if(t->left) {t->left->val += t->val;st.push(t->left);}
            if(t->right){t->right->val += t->val;st.push(t->right);}
        }
        return false;
    }
};

#118 Pascal’s Triangle
要求：杨辉三角，返回数组的集合。行数为输入的整数
思路1：就是建立二维数组，每一行初始全为1，然后逐渐赋值其他。代码没写出来。
参考了大神博客园:Grandyang

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> res(numRows, vector<int>());
        for(int i = 0 ; i<numRows; ++i)
	    {
		    res[i].resize(i+1,1);
		    for(int j = 1; j<i; ++j){
			res[i][j]= res[i-1][j-1] +res[i-1][j];}
		}
	return res;
    }
};

#119 Pascal’s Triangle II
要求：输出杨辉三角的指定索引行。
思路1：杨辉三角1改编即可。需要依赖于杨辉三角题已解。只需要输出特定行。

class Solution {
public:
    vector<int> getRow(int rowIndex) {
         vector<vector<int>> res(rowIndex+1, vector<int>());
        for(int i = 0 ; i<rowIndex+1; ++i)
	    {
		    res[i].resize(i+1,1);
		    for(int j = 1; j<i; ++j){
			res[i][j]= res[i-1][j-1] +res[i-1][j];}
		}
	return res[rowIndex];
    }
};

#121 Best Time to Buy and Sell Stock
要求：给定一个数组，按照某一天购买，后续卖出的差值，求最大化利润。无利润则返回0
思路1：笨办法，二重循环，显然不满足题意，无法通过大用例

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int maxProfit = 0; 
        for(int i = 0 ; i<prices.size();i++)
        {
            for(int j = i+1 ; j<prices.size();j++)
            {
                int result = prices[j]- prices[i];
                maxProfit = max(result, maxProfit);
            }
        }
        return maxProfit;
    }
};

参考了大神博客园：Grandyang
思路2：对于二重循环的垃圾想法，还是要早早放弃啊，这种方法才是真的好

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res = 0, buy = INT_MAX;
        for (int price : prices) {
            buy = min(buy, price);
            res = max(res, price - buy);
        }
        return res;
    }
};

菜鸟一枚，欢迎大家批评指正，谢谢~