写在前面

Emmm… 总之，这些属于个人在学习算法中记录的思考过程和总结笔记。

因为我还属于萌新，关于算法的学习都是通过做题，和看网络上的视频，或者是想不出来的题参考了大家的题解，再通过自己的思考总结出来的。
我的解法以及思考还属于萌新阶段，希望不要误导大家，如果有错误的话，也希望大佬指出，如果你能从我的解法或思路中获得启发，我会很开心。通过不断的学习进步，我可能会有新的思考，也会更新以前不成熟甚至不太对的笔记。

struct TreeNode
{
    TreeNode * left;
    TreeNode * right;
    int val;
}

1. 二叉树的遍历

先序遍历的实现有两种不同思路

第一个算法是DFS的一种二叉树树的特例，与层次遍历类似（层次遍历使用队列，这种相似性源于BFS和DFS的相似性），并且有助于我们实现后序遍历的一个版本。具体算法如下：

1. 首先将树根压栈。
2. 在栈不为空的情况下，将当前指针更新为栈顶元素，弹出栈顶元素并加入到结果数组中，在当前节点的右孩子不为空的情况下，将其压入栈中，在root的左孩子不为空的情况下，压入栈中。
3. 返回第2步

第二个算法与中序遍历类似,思路是不管是前中后序哪一种遍历方式，实际上都是从树根开始，然后先向左子树深入，再向右子树深入的过程，且每个节点都会遇到3次（从父节点向下遍历是第一次遇到，左遍历完返回时是第二次遇到，右遍历完返回时是第二次遇到），不同的是访问节点的顺序，先序是第一次，中序是第二次，后序是第三次，因此按这种思路，它们的代码逻辑应该很相似，区别在于处理节点的时机。而后序之所以难，是因为它是第三次访问时才处理节点，而我们利用栈结构，入栈是第一次，出栈是第二次，没有第三次的时机。以下为具体算法（对于先序遍历，栈中的元素是都已经处理过的元素)：

1. 当栈不为空且当前指针不为空时，进入循环

2. 2.1 如果当前指针不为空，将指针所指的节点压入栈中，并处理这个节点(加到结果数组中），当前指针向左移动
   2.2 如果当前指针为空，弹出栈顶的元素，并将当前指针更新为这个弹出元素的右孩子

3. 返回第一步
4. 此时栈和当前指针都为空，处理完所有元素（所有元素加到结果数组中)，返回结果数组

/*先序遍历*/

vector<int> preOrder(TreeNode* root)
{
    vector<int> res;
    if (root == nullptr) return res;
    stack<TreeNode *> s;
    s.push(root);
    while (!s.empty())
    {
        root = s.top();
        res.push_back(root->val);
        s.pop();
        if (root->right != nullptr)
            s.push(root->right);
        if (root->left != nullptr)
            s.push(root->left);
    }
    return res;
} 

  vector<int> preOrder(TreeNode* root) {
    vector<int> res;
    if(root == nullptr) return res;
    stack<TreeNode *> s;
    while(!s.empty() || root!=nullptr)
    {
        if(root != nullptr)
            {
                s.push(root);
                res.push_back(root->val);
                root = root->left;
            }
        else 
        {
            root = s.top()->right;
            s.pop();

        }
    }
    return res;
    }

对于中序遍历，栈顶元素弹出时是被第二次访问的时候
中序遍历的算法步骤为：

1. 当栈不为空且当前指针不为空时，进入循环

2. 2.1 如果当前指针不为空，将指针所指的节点压入栈中，当前指针向左移动
   2.2 如果当前指针为空，弹出栈顶的元素，处理这个栈顶元素，并将当前指针更新为这个弹出元素的右孩子

3. 返回第一步
4. 此时栈和当前指针都为空，处理完所有元素（所有元素加到结果数组中)，返回结果数组

/*中序遍历*/ 
vector<int> inOrder(TreeNode *root)
{
    vector<int> res;
    if(root == nullptr) return res;
    stack<TreeNode *> s;

    while(!s.empty() || root!=nullptr) 
    {
        if(root != nullptr)
            {
                s.push(root);
                root = root->left;
            }
        else 
        {
            root = s.top();
            res.push_back(root->val);
            s.pop();
            root = root->right;
        }
    }
    return res;
}

后序遍历由于目前没有细看最简洁的且空间复杂度更低的算法，采用一种投机取巧的方法，我们知道后序遍历的顺序是左右根，如果我们能得到根右左的顺序，它的反转就是后序遍历，根据先序遍历根左右的第一个算法，很轻松的得到根右左的算法，借助第二个栈反转即得到后序遍历：

1. 首先将树根压栈。
2. 在栈不为空的情况下，将当前指针更新为栈顶元素，弹出栈顶元素并加入到另一个辅助栈中，在当前节点的右孩子不为空的情况下，将其压入栈中，在root的左孩子不为空的情况下，压入栈中。
3. 返回第2步
4. 此时栈为空，将辅助栈的元素弹出到结果数组中，并返回。

/*后序遍历*/
vector<int> preOrder(TreeNode* root)
{
    vector<int> res;
    if (root == nullptr) return res;
    stack<TreeNode *> s;
    stack<TreeNode *> s2;
    s.push(root);
    while (!s.empty())
    {
        root = s.top();
        s2.push(root);
        s.pop();
        if (root->left != nullptr)
            s.push(root->left);
        if (root->right != nullptr)
            s.push(root->right);
    }
    while(!s2.empty())
    {
        res.push_back(s2.top()->val);
        s2.pop();
    }
    return res;
} 

层次遍历在介绍先序遍历的第一种方法的时候已经提到过，这里就不详述了

/*层次遍历*/
 vector<int> printFromTopToBottom(TreeNode* root) {
        vector<int> res;
        if(root == nullptr) return res;
        queue<TreeNode *> q;
        q.push(root);

        while(!q.empty())
        {
            root = q.front();
            q.pop();
            res.push_back(root->val);
            if(root->left != nullptr)
                q.push(root->left);
            if(root->right != nullptr)
                q.push(root->right);
        }
        return res;
    }

2.与二叉树有关的题目：

题目： 重建二叉树
来源： AcWing 18||剑指offer
思路： 由题意需要根据前序遍历和中序遍历的结果重建二叉树，根据两种遍历的特点，前序遍历顺序是根左右，中序遍历顺序是左根右。我们在前序遍历中，得到整棵树根的位置，建立根节点，再在中序遍历中找到这个根（因为节点的值互不相同）,那么，在中序遍历根左边的就是其左子树，在中序遍历根右边的就是其右子树，在其左右子树中继续递归的建立每个节点。这是一种典型的递归思路（别忘了终止条件）

 /*根据先序遍历和中序遍历重建二叉树*/
 TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        //省略了非法的先序遍历数组和中序遍历数组，如两者大小不相等，或者两者元素不相等 等等。
        return buildTree(preorder,inorder,0,preorder.size()-1,0,inorder.size()-1);
    }
//pl和pr是指先序遍历数组的范围，il和ir是指中序遍历数组的范围
 TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder,int pl,int pr,int il,int ir)
 {
     if(pl > pr || il > ir)//如果范围已经非法
        return nullptr;

     TreeNode *node = new TreeNode(preorder[pl]);
     for(int i = il;i<=ir;i++)
     {
         if(preorder[pl] == inorder[i])
         {
             node->left =   buildTree(preorder,inorder,pl+1,pl+i-il,il,i-1);
             node->right =  buildTree(preorder,inorder,pl+i-il+1,pr,i+1,ir);
             break;
         }
     }
     return node;
 }

题目： 含父节点的二叉树的下一个节点
来源： AcWing 19||剑指offer
思路： 中序遍历的顺序是左根右，所以，如果一个节点有右子树，那么它的下一个节点就是它右子树的最左节点；如果一个节点没有右子树，那么它的后继节点在它的上方，假设该节点为node，如果node的父节点以node为左孩子，则其父节点就是它的后继，否则，node继续向上移动，直到满足条件。如果最终也不满足条件，说明该节点为二叉树的最后一个节点，没有后继节点。此题主要是考察中序遍历的定义。

TreeNode* inorderSuccessor(TreeNode* p)
{
    if(p->right != nullptr)
        {
            p = p->right;
            while(p->left != nullptr)
            {
                p = p->left;
            }
            return p;
        }
    else 
    {
        while(p->father!=nullptr &&  p->father->left != p)
        {
            p = p->father;
        }

        return p->father;
    }

}

题目：树的子结构
来源： AcWing37||剑指offer
思路：按照递归去思考，pRoot1是第一颗树中任意一个节点，大的思路是，对pRoot1来说，看看它本身是否和pRoot2的根节点相同，在是的情况下，判断以该节点为起点是否和pRoot2存在相同的树结构，得到结果，如果不满足，则判断其左右子树是否满足条件，然后综合三个结果，返回结果给上层。同样的，如果按照递归的方式思考，如何判断以该节点为起点是否和pRoot2存在相同的树结构呢？如果pRoot1和pRoot2的值相等，那么考虑pRoot2的左右子树是否分别是pRoot1的左右子树的子结构，只有在本身值相等且两者都是的情况下，才能说pRoot2是pRoot1的子结构。注意终止条件的思考。

    bool hasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)  //整颗树上是否存在一个起点，使得pRoot2与pRoot1有相同的树结构
 {
    bool result = false;
    if(pRoot2 == nullptr) return false; //由题意
    if(pRoot1 == nullptr) return false;//终止条件：到达pRoot1叶子节点的左右孩子后，给上层返回false

    //只要满足3个if中的一个，则返回true
        if(pRoot1->val == pRoot2->val)      //以当前节点为起点，pRoot2是否存在与pRoot1相同的树结构
            result = isSame(pRoot1,pRoot2); 
        if(!result)
            result = hasSubtree(pRoot1->left,pRoot2);   //左子树上是否存在一个起点，使得pRoot2与pRoot1有相同的树结构
        if(!result)
            result = hasSubtree(pRoot1->right,pRoot2);  //右子树上是否存在一个起点，使得pRoot2与pRoot1有相同的树结构

    return result;
}
//以当前两树的root为根，判断pRoot2是否是pRoot1的子结构
bool isSame(TreeNode* pRoot1,TreeNode* pRoot2) 
{
    //终止条件： 1. pRoot2如果为空，说明pRoot2是pRoot1的子结构
    // 2. 如果pRoot1为空，而pRoot2不为空，说明pRoot2不是pRoot1的子结构
     if(pRoot2 == nullptr) return true;  
     if(pRoot1 == nullptr) return false; 


     if(pRoot1->val == pRoot2->val && isSame(pRoot1->left,pRoot2->left)&&isSame(pRoot1->right,pRoot2->right)) 
         return true;     
     else return false;

}