1. 二叉树创建字符串

题目链接：606. 根据二叉树创建字符串 - 力扣（LeetCode）

题目描述：给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。空节点使用一对空括号对 "()" 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

 题目：给一个根节点，前序遍历：根节点，左子树，右子树。给了一个根节点，是TreeNode*,最后的返回值是string。

思路：1.使用to_string进行一次转换（root->val)

           2.前序遍历：根节点，左节点，右节点。

• 如果左节点不为空，将这个根节点先拿到，然后递归遍历这个节点的左子树。
• 如果左节点为空，右节点不为空。拿到右节点，再去递归遍历右节点的左子树。
• 如果左节点为空，右节点为空，返回一个空字符串。

左右节点只要有一个不为空，就不能省略左节点的()。判断条件是if(root->left || root->right)。已经遍历完所有的根节点和左子树。接下来要访问右子树，如果右节点不为空，就去访问右节点的右子树并加上()。

class Solution {
public:
    string tree2str(TreeNode* root) {

        if(root == nullptr)
            return "";
        string str = to_string(root->val);
        
        //如果左节点不为空，遍历左节点的左子树
        //如果左节点为空，遍历右节点的左子树
        if(root->left ||  root->right)
        {
            str +='(';
            str+= tree2str(root->left);
            str+= ')';
        }
       
       //遍历右节点的右子树
       if(root->right)
       {
           str +='(';
           str+=tree2str(root->right);
           str+=')';
       }

        return str;
    }
};

2. 二叉树的分层遍历I

题目链接：https://leetcode.cn/problems/binary-tree-level-order-traversal/

题目描述：给一个二叉树的根节点root,返回层序遍历。逐层从左到右访问所有节点

 分析：形参是root,返回值是一个vector<vector<int>>， 一层放入一个vector<int>里面，出完一层，放入vector<vector<int>>中，所以要定义两个vector,vector<int> v, vector<vector<int>> vv。判断一层是否出完：用一个levelsize去判断，队列为空的时候，这层就出完了。那如何去统计这个levelsize?如何判断所有的节点都出完了？

思考1：当 3出队列，第一层出完，此时队列为空，9，20入队列，队列中节点的个数就是这层节点数，9出队列，20出队列，此时队列为空，15，7入队列。队列中节点的大小就是这层节点数。

思考2：当队列为空，所有的节点都出完了，可以reutrn vv。

class Solution{
pubilc:

vector<vector<int>> levelOrder(TreeNode * root)
{
   // vector<int> v;
    vector<vector<int>> vv;
    int levelsize = 0;
    queue<TreeNode *> q;
    
    //入队列，空的就不入了
    if(root)
     {    
         q.push(root);
        levelsize = 1;
      }
    
    //当队列中还有数据，就继续出 
    while(!q.empty())
    {
        //在这里定义v，每次上来v都是空的
          vector<int > v;
        //一层一层出
        while(levelsize--)
        {
            //这里要用front 因为使用root，pop之后，就无法更新
            //front每次都是头节点
          TreeNode * front =  q.front();
            v.push(front ->val);
            q.pop();
            if(front ->left)
                q.push(front->left);
            if(q->right)
                q.push(front->right);
         }
    
        //一层出完，统计当前队列中的个数
        levelsize = q.size();
        //放入vv中
        vv.push_back(v);
    }
        
        return vv;
}
};

3. 二叉树的分层遍历II

题目链接：力扣

题目描述：给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

分析:这道题也是层序遍历，和上一道题不同就是自底向上遍历，观察以下它的输出，和正序遍历就是一个逆置的关系，所以使用一个reverse即可解决问题。

reverse(vv.begin(),vv.end());

4. 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先

题目描述：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

题目链接：236. 二叉树的最近公共祖先 - 力扣（LeetCode）

分析：首先先看到的是根节点，如果这两个节点都在根节点的左子树，那么就继续判断根节点的左节点，再去判断这两个节点是否在这个节点的左，右子树，如果是，则这个节点就是最近的公共祖先，如果不是，那么继续判断，如果在右树，就找当前节点的右节点，继续判断。使用递归的思想

class Solution {
public:
    bool IsInTree(TreeNode * root, TreeNode * x)
    {
        if(root == nullptr)
            return false;
        if(x == root)
            return true;
        else
        {
          return  IsInTree(root->left,x) || IsInTree(root->right,x);
        }
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == nullptr)
            return nullptr;

        //1.一个是根节点，一个是子节点，返回根节点
        if(p == root || q == root)
            {
                return root;
            }
        //2.一个在左，一个在右
        //要判断p,q在左还是右，用一个bool 递归
       bool pLeft = IsInTree(root->left,p);
       bool pRight = !pLeft;  //这里判断一个子树就可以，右树取反
       bool qLeft = IsInTree(root->left,q);
       bool qRight = !qLeft;

       if(pLeft&&qRight || pRight&& qLeft)
            return root;
       else if(pLeft && qLeft )
            return lowestCommonAncestor (root->left,p,q);
       else if(pRight && qRight)
            return lowestCommonAncestor(root->right,p,q);

        return 0;
    }
};

5. 二叉树搜索树转换成排序双向链表

题目描述：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

将一个 二叉搜索树 就地转化为一个 已排序的双向循环链表 。

对于双向循环列表，你可以将左右孩子指针作为双向循环链表的前驱和后继指针，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

特别地，我们希望可以 就地 完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中最小元素的指针。

分析：

思路1：中序遍历，将节点放进vector中，再改链接关系（不符合空间复杂度O（1））

思路2：中序遍历这棵树，同时记录前驱节点prev，cur的左指针指向前驱。prev的右指针指向cur。这个思路的精华就是cur出现在不同的栈帧中。prev只用了一个，所以使用的引用。

class Solution {
public:
	void InorderConvert(TreeNode * cur,TreeNode *&prev)
	{
		if(cur == nullptr)
			return;
		InorderConvert(cur->left,prev);
		//这里cur出现的顺序就是中序
		cur->left = prev;
		if(prev)
			prev->right = cur;
		prev = cur;
		InorderConvert(cur->right,prev);
	}


    TreeNode* Convert(TreeNode* pRootOfTree) {
		TreeNode * prev = nullptr;
        InorderConvert(pRootOfTree,prev);

		//找到最左的节点就是头
		TreeNode * head = pRootOfTree;
		while(head && head->left)
		{
			head = head->left;
		}

		return head;
    }
};

6. 根据一棵树的前序遍历与中序遍历构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

分析：前序的顺序是根，左，右。通过前序可以确定出根节点

           中序的顺序是左，根，右。根据中序可以确定出左右子区间

class Solution {
public:
      TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder , int & prei,int inbegin, int inend) {
          if(inbegin >inend)
            return nullptr;
          TreeNode * root = new TreeNode(preorder[prei]);
          //分割出左右子区间 在中序里面找根
            int rooti = inbegin;
            while(rooti <= inend)
            {
                if(inorder[rooti] == preorder[prei])
                    break;
                else
                    rooti++;
            }
            //[inbegin rooti-1] rooti [rooti+1 inend] 
            ++prei;
          root->left = _buildTree(preorder,inorder,prei,inbegin,rooti-1);
          root->right = _buildTree(preorder,inorder,prei,rooti+1,inend);
          return root;

      }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int i = 0;
      
       return _buildTree(preorder,inorder,i,0,inorder.size()-1);


    }
};