606. 根据二叉树创建字符串

要点：前序遍历，当左子树为空时，右结点有数字时要给左边加括号

class Solution {
public:
    string tree2str(TreeNode* root) {
        string s;//创建一个字符串
        if(root==nullptr)
        {
            return s;
        }
        s+=to_string(root->val);//保存当前结点，转换为字符串
        if(root->left)//左子树不为空，继续往左子树走
        {
            s+="(";
            s+=tree2str(root->left);
            s+=")";
        }
        else if(root->right)//当左子树为空右子树不为空
        {
            s+="()";
        }

        if(root->right)//遍历右边
        {
            s+="(";
            s+=tree2str(root->right);
            s+=")";
        }//不需要加（）
        return s;

    }
};

102. 二叉树的层序遍历

层次遍历想到用队列将一层一层的数据存入在拿出来

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> vv;
        queue<TreeNode*> q;
        if(root)
        {
            q.push(root);//存入第一个结点
        }
       
        while(!q.empty())//判空
        {
            vector<int> v;
            int lenght=q.size();
            for(size_t i = 0;i<lenght;i++)//用一个值去控制输出的层次
            {
            TreeNode* front = q.front();//将存入的数提取
            v.push_back(front->val);//给一维数组赋值
            q.pop();//弹出
            if(front->left)//当有左值存入
                q.push(front->left);


            if(front->right)//当有右值存入
                q.push(front->right);
            
            }
           vv.push_back(v);//将该一维数组存入，二维数组中
        }
         return vv;
    }
};

107. 二叉树的层序遍历 II

和上一道题相反，只需要将结果反转最后的二维数组就可以了reverse(开始的迭代器和结束的迭代器)

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root)
    {
         vector<vector<int>> vv;
        queue<TreeNode*> q;
        if(root)
        {
            q.push(root);//存入第一个结点
        }
       
        while(!q.empty())//判空
        {
            vector<int> v;
            int lenght=q.size();
            for(size_t i = 0;i<lenght;i++)//用一个值去控制输出的层次
            {
            TreeNode* front = q.front();//将存入的数提取
            v.push_back(front->val);//给一维数组赋值
            q.pop();//弹出
            if(front->left)//当有左值存入
                q.push(front->left);


            if(front->right)//当有右值存入
                q.push(front->right);
            
            }
           vv.push_back(v);//将该一维数组存入，二维数组中
        }
        reverse(vv.begin(),vv.end());
         return vv;
    }
};

236. 二叉树的最近公共祖先

分析：这里是二叉搜索树只要知道左边和右边中间的就是公共祖先

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

        if(root==p||root==q)
            return root;
        
        bool pInleft,pInright,qInleft,qInright;//这里代表pq在左边还是右边
        pInleft=Find(root->left,p);//这里也是递归，寻找p在那边
        pInright=!pInleft;

        qInleft=Find(root->left,q);//这里也是递归，寻找q在那边
        qInright=!qInleft;

        if((pInleft && qInright)||((qInleft && pInright)))
        {
            return root;//当pq在左右两边时root就是祖先
        }
        if(qInleft && pInleft)//当pq都在左边
        {
            return lowestCommonAncestor(root->left,p,q);
        }

        if(qInright && pInright)//当pq都在右边
        {
            return lowestCommonAncestor(root->right,p,q);
        }
        return NULL;
    }
};

 

二叉搜索树与双向链表_牛客题霸_牛客网 (nowcoder.com)

class Solution {
public:
    void convertList(TreeNode* cur,TreeNode*& prev)//这里为什么要加&，递归到最后改变cur并没有改变所以要加&，才知道用同一个
	{
		if(cur==NULL)
		{
			return;
		}
		convertList(cur->left,prev);
		cur->left=prev;

		if(prev)
		   prev->right = cur;

		prev =cur;

		convertList(cur->right,prev);

	}
    TreeNode* Convert(TreeNode* pRootOfTree) 
	{
		TreeNode* prev = NULL;
		convertList(pRootOfTree,prev);

		TreeNode* head = pRootOfTree;
		while(head && head->left)
		{
			head=head->left;
		}
		return head;
    }
};