'算法学习'

本篇用于记录刷力扣时值得参考的算法题，主语言为C++

二叉树的中序遍历

**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

    void inorder(TreeNode* root,vector<int>& res)
    {
        if(!root)
        {
            return; //当前节点为空的话跳出该次递归
        }
        inorder(root->left,res); /*递归调用，将root指针指向当前节点的左子节点。当遇到最左边的子节点时
                                  再执行inorder的话，此时root指针会指向空，此时便会触发上面的if判断，
                                  跳出该次递归，返回上一层的递归。那么此时root便指向了最靠左的子节点
                                 */
        res.push_back(root->val); //root指针指向最左子节点后，将该节点的值压入容器res中
        inorder(root->right,res); //若该最左子节点他还有个右孩子的话，root便会指向它，再次执行上边的流程
    }
    vector<int> inorderTraversal(TreeNode* root) {
           vector<int> res;  //定义一个空的vector容器res
           inorder(root,res);  //从根节点开始执行递归
           return res;   //最后返回一个包含中序遍历的结果的res
    }
};

617.合并二叉树

我觉得利用递归来建树这个思想很值得学习

TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
          if(root1==nullptr)  //if用于判断是否到达叶节点，到达后跳出该层递归，返回上层节点。
                              //还有一个作用是当A树的该节点为空，B树的该节点非空时,null + value = value，所以直接返回非空节点的值 
          {
            return root2;  
          }
          if(root2==nullptr)
          {
            return root1;
          }
          auto merged = new TreeNode(root1->val + root2->val);  //新建一个新节点，用于储存两个树的节点相加后的值
          merged->left = mergeTrees(root1->left,root2->left);  /*建立左子树部分，并且利用递归的方式创建左孩子的孩子节点
                                                                理解这一部分的递归调用很关键 */
          merged->right = mergeTrees(root1->right,root2->right);
          return merged;
    }

总结来说的运行逻辑是这样的:

创建一个merged节点(类型为结构体TreeNode,包含了val和left、right的指针)(这里的auto也很有意思，可以去了解一下)

merged节点的值等于root1的值+root2的值

目光聚焦到merged节点的左孩子,怎么得到它的值？再执行一遍mergeTrees函数！不过此时函数中的参数应该设置为root1,root2的左孩子

如果还没到叶节点，那么这个递归会一直进行下去

若到达了叶节点，说明这颗合成树的root->left->left->left……依旧构造完了

叶子节点弹出递归栈，返回它的父节点，如果此时父节点的右孩子为非空的话，继续执行merged->right的递归

反复的弹出递归栈…执行merged->right…….

理解递归栈的调用和程序的执行顺寻很重要，比如执行递归调用时，当前的程序在什么位置？执行递归调用的话会回到什么位置？执行完递归后又会回到什么位置？这段代码会有助于理解递归栈的调用逻辑

for循环的简化

for(int i=0;i<prices.size();i++)
    {
        if(prices[i]<minbuy)
        {
            minbuy = prices[i];  //找到最小值
        }
        profit = prices[i] - minbuy;
        if(profit>maxprofit)
        {
            maxprofit = profit;  //找到最大值
        }
    }

看起来就很冗余，可以用 : 来代替for循环中的条件，并且最大最小值可与用max(a,b),min(a,b)来完成

for(int i:prices) //等于:for(int j = 0;j<prices.size();j++)    i = price[j]
   {   
       minbuy = min(minbuy,i);  //比if判断要简洁多了
       maxprofit = max(maxprofit,i-minbuy);
     
   }