当前位置： 首页 > news >正文

从零备战蓝桥杯——二叉树及相关题目(基础篇)

news 来源：原创 2024/5/3 10:30:08

双非刷leetcode备战2023年蓝桥杯，qwq加油吧，无论结果如何总会有收获！一起加油,我是跟着英雄哥的那个思维导图刷leetcode的，大家也可以看看所有涉及到的题目用leetcode搜索就可以哦，因为避让添加外链，一起加油！！！请添加图片描述

文章目录

    • @[toc]
  • 纯基础部分：
    • 二叉树的初始化
      • 二叉树的创建
      • 二叉树的遍历
        • 前序遍历二叉树（先根再左再右）
        • 中序遍历二叉树（先左再根再右）
        • 后序遍历二叉树（先左再右再根）
      • 二叉树的非递归遍历：
        • 非递归先序遍历
        • 非递归后序遍历
        • 非递归中序遍历
  • 本文全部代码：
  • 相关leetcode题目：
    • 前序遍历
      • 144. 二叉树的前序遍历
    • 深度优先遍历：
      • 257. 二叉树的所有路径
      • 同为深度优先遍历的一个题:129. 求根节点到叶节点数字之和
      • 又深度优先遍历：剑指 Offer II 045. 二叉树最底层最左边的值
    • 后序遍历
      • ※ 后序遍历 剑指 Offer II 047. 二叉树剪枝
      • 979. 在二叉树中分配硬币(后序,较难)
    • 层序遍历
      • 二叉树的层序遍历 102. 二叉树的层序遍历
        • DFS做法：
        • BFS做法（广度优先搜索）：
      • 107. 二叉树的层序遍历 II
      • 剑指 Offer II 046. 二叉树的右侧视图 （199. 二叉树的右视图）
    • 二叉树的插入
      • 919. 完全二叉树插入器
    • 二叉树的构造
      • 105. 从前序与中序遍历序列构造二叉树
      • 449. 序列化和反序列化二叉搜索树
    • LCA最近公共祖先
      • 二叉搜索树版
      • LCA非二叉树版:

纯基础部分：

二叉树的初始化

首先我们要先声明一个二叉树类里面要有数据节点，左节点，右节点。

#include <iostream>
#include <vector>
using namespace std;

class BinaryTree
{
public:
    char data;
    BinaryTree* left;
    BinaryTree* right;
};

二叉树的创建

递归创建二叉树(‘#’表示节点为空)：

void CreatBinaryTree(BinaryTree* &root) {//就相当于建立了一个root指针然后让root指针当一个tree的别名，root指针的本质就是对象指针
	char c;
	cin >> c;
	if (c == '#')	//当遇到#时，令树的根节点为NULL，从而结束该分支的递归
		root = NULL;
	else
	{
		root = new BinaryTree;//用指针存放new出来的对象的地址这个指针就相当于新对象的指针。
		root->data = c;	//指针指向对象中的data也可以写成(*root).data
		CreatBinaryTree(root->left);//递归构建左子树
		CreatBinaryTree(root->right);//递归构建右子树
	}
}

二叉树的遍历

前序遍历二叉树（先根再左再右）

//前序遍历二叉树

void Preorder(BinaryTree* root, vector<char> &path)//path作为形参的传递方式
{
	if (root != NULL) {
		path.push_back(root->data);//在vector的末尾添加一个数就是按序排列（后来的插在后面）
		Preorder(root->left, path);//访问左儿子
		Preorder(root->right, path);//访问右儿子
	}
}//调用完了vector中就有数字了~

中序遍历二叉树（先左再根再右）

//中序遍历二叉树

void Inorder(BinaryTree* root, vector<char> &path)//path作为形参的传递方式
{
	if (root != NULL) {
		Preorder(root->left, path);//访问左儿子
        path.push_back(root->data);//在vector的末尾添加一个数就是按序排列（后来的插在后面）
		Preorder(root->right, path);//添加右儿子
	}
}//调用完了vector中就有数字了~

后序遍历二叉树（先左再右再根）

//后序遍历二叉树

void Postorder(BinaryTree* root, vector<char> &path)//path作为形参的传递方式
{
	if (root != NULL) {
		Preorder(root->left, path);//访问左儿子
        Preorder(root->right, path);//访问右儿子
        path.push_back(root->data);//在vector的末尾添加这个节点 就是按序排列（后来的插在后面）
		
	}
}//调用完了vector中就有数字了~

整个代码如下

#include<iostream>
#include<vector>

using namespace std;

//声明类
class BinaryTree {
public:
	char data;
	BinaryTree* left, * right;
};

//按照前序遍历创建二叉树
void CreatBinaryTree(BinaryTree* &root) {//就相当于建立了一个root指针然后让root指针当一个tree的别名，root指针的本质就是对象指针
	char c;
	cin >> c;
	if (c == '#')	//当遇到#时，令树的根节点为NULL，从而结束该分支的递归
		root = NULL;
	else
	{
		root = new BinaryTree;//用指针存放new出来的对象的地址这个指针就相当于新对象的指针。
		root->data = c;	//指针指向对象中的data也可以写成(*root).data
		CreatBinaryTree(root->left);//递归构建左子树
		CreatBinaryTree(root->right);//递归构建右子树
	}
}

void PrintBinaryTree(vector<int> path);//声明打印二叉树函数

//前序遍历二叉树

void Preorder(BinaryTree* root, vector<char> &path)//path作为形参的传递方式
{
	if (root != NULL) {
		path.push_back(root->data);//在vector的末尾添加一个数就是按序排列（后来的插在后面）
		Preorder(root->left, path);//访问左儿子
		Preorder(root->right, path);//访问右儿子
	}
}//调用完了vector中就有数字了~

//中序遍历二叉树

void Inorder(BinaryTree* root, vector<char> &path)//path作为形参的传递方式
{
	if (root != NULL) {
		Inorder(root->left, path);//访问左儿子
        path.push_back(root->data);//在vector的末尾添加一个数就是按序排列（后来的插在后面）
		Inorder(root->right, path);//添加右儿子
	}
}//调用完了vector中就有数字了~

//后序遍历二叉树

void Postorder(BinaryTree* root, vector<char> &path)//path作为形参的传递方式
{
	if (root != NULL) {
		Postorder(root->left, path);//访问左儿子
        Postorder(root->right, path);//访问右儿子
        path.push_back(root->data);//在vector的末尾添加这个节点 就是按序排列（后来的插在后面）

	}
}//调用完了vector中就有数字了~
//打印函数
void PrintBinaryTree(vector<char> path) {
	int n = path.size();
	for (int i = 0;i < n;++i) {
		cout << path[i]<<' ';
	}
	cout<<endl;
}


int main()
{
	vector<char> path1, path2, path3;
	cout << "请使用前序遍历创建二叉树（若节点为空输入#代替）：" << endl;
	BinaryTree* root = NULL;
	CreatBinaryTree(root);
	cout << "二叉树创建完成！" << endl;
	cout << "前序遍历二叉树结果为：" << endl;
	Preorder(root, path1);
	PrintBinaryTree(path1);
	cout << "中序遍历二叉树结果为：" << endl;
	Inorder(root, path2);
	PrintBinaryTree(path2);
	cout << "后序遍历二叉树结果为：" << endl;
	Postorder(root, path3);
	PrintBinaryTree(path3);

	return 0;
}

输出结果为:

请添加图片描述

这样二叉树最简单的部分就学完了~~

测试数据：

1
2
3
# #
4
# #
5
6
# #
7
# #

二叉树的非递归遍历：

非递归先序遍历

怎么实现？先准备一个栈，然后把头解点放进去

  1. 从栈中弹出一个节点
  2. 打印处理节点
  3. 先右再左
  4. 重复
//先序遍历非递归
void preOrderUnRecur (BinaryTree root){
    cout<< "非递归先序遍历" << endl;
	BinaryTree *root1 = new BinaryTree;
	*root1 = root;
    if (root1 != NULL)
    {
		
		stack<BinaryTree> stack;
		stack.push(*root1);
		while (!stack.empty())
		{

			*root1 = stack.top();
			stack.pop();
			cout << root1->data <<' ';
			if (root1->right != NULL)
			{
				stack.push(*root1->right);
			}
			if (root1-> left != NULL)
			{
				stack.push(*root1->left);
			}
		}
		cout<< endl; 
            
    }

}

非递归后序遍历

  • 先序遍历的顺序不是头左右嘛，把左右换一下不就是头右左了嘛把头右左压到另一个栈里面不就是左右头了嘛，左右头不就是后序遍历了嘛~ 再把那个栈输出一遍不就完事了嘛~
//后序遍历非递归
void postOrderUnRecur(BinaryTree * root){
 cout<< "非递归后序遍历" << endl;
		BinaryTree *root1 = root;
    if (root1 != NULL)
    {

		stack<BinaryTree *> stack,stack2;
		stack.push(root1);
		while (!stack.empty())
		{

			root1 = stack.top();
			stack.pop();
			stack2.push(root1);
			if (root1-> left != NULL)
			{
				stack.push(root1->left);
			}
			if (root1->right != NULL)
			{
				stack.push(root1->right);
			}

		}
		while (!stack2.empty())
		{
			cout << stack2.top()->data << " ";
			stack2.pop();
		}

		cout<< endl;

    }
}

非递归中序遍历

逮住一棵树，先把左边界压到栈里去在弹出每一个节点的过程中让他的右树也这么干

  • 每棵子树，整棵树左边界进栈，然后依次弹出节点的过程打印中对弹出节点的右树重复
void inOrderUnRecur (BinaryTree* root){
    cout<< "非递归中序遍历" << endl;
	BinaryTree *root1 = root;//建个指针对象指向根节点
	stack<BinaryTree*> stack2;//建个栈
    if (root1 != NULL)//如果根节点不为空的话
    {

		while ( !stack2.empty() || root1)//当栈不为空并且根节点不为空时
		{
			if (root1)//如果这个节点不为空就把他压栈并且去看看他的左节点(不停地把左边界进栈)
			{
				stack2.push(root1);
				root1 = root1->left;
			}
			else//左边界为空了就开始弹出节点
			{
                root1 = stack2.top();
				cout << root1->data << ' ';
				stack2.pop();//弹出节点并打印
				root1 = root1->right;//对右树周而复始压左树
			}

		}


    }
		cout << endl;
}
//前左再头的弄出来但是右树后干这件事

本文全部代码：

#include<iostream>
#include<vector>
#include<stack>

using namespace std;

//声明类
class BinaryTree {
public:
	char data;
	BinaryTree* left, * right;
};

stack<BinaryTree> stack2;
//按照前序遍历创建二叉树
void CreatBinaryTree(BinaryTree* &root) {//就相当于建立了一个root指针然后让root指针当一个tree的别名，root指针的本质就是对象指针
	char c;
	cin >> c;
	if (c == '#')	//当遇到#时，令树的根节点为NULL，从而结束该分支的递归
		root = NULL;
	else
	{
		root = new BinaryTree;//用指针存放new出来的对象的地址这个指针就相当于新对象的指针。
		root->data = c;	//指针指向对象中的data也可以写成(*root).data
		CreatBinaryTree(root->left);//递归构建左子树
		CreatBinaryTree(root->right);//递归构建右子树
	}
}

void PrintBinaryTree(vector<int> path);//声明打印二叉树函数

//前序遍历二叉树

void Preorder(BinaryTree* root, vector<char> &path)//path作为形参的传递方式
{
	if (root != NULL) {
		path.push_back(root->data);//在vector的末尾添加一个数就是按序排列（后来的插在后面）
		Preorder(root->left, path);//访问左儿子
		Preorder(root->right, path);//访问右儿子
	}
}//调用完了vector中就有数字了~

//中序遍历二叉树

void Inorder(BinaryTree* root, vector<char> &path)//path作为形参的传递方式
{
	if (root != NULL) {
		Inorder(root->left, path);//访问左儿子
        path.push_back(root->data);//在vector的末尾添加一个数就是按序排列（后来的插在后面）
		Inorder(root->right, path);//添加右儿子
	}
}//调用完了vector中就有数字了~

//后序遍历二叉树

void Postorder(BinaryTree* root, vector<char> &path)//path作为形参的传递方式
{
	if (root != NULL) {
		Postorder(root->left, path);//访问左儿子
        Postorder(root->right, path);//访问右儿子
        path.push_back(root->data);//在vector的末尾添加这个节点 就是按序排列（后来的插在后面）

	}
}//调用完了vector中就有数字了~
//打印函数
void PrintBinaryTree(vector<char> path) {
	int n = path.size();
	for (int i = 0;i < n;++i) {
		cout << path[i]<<' ';
	}
	cout<<endl;
}
//先序遍历非递归
void preOrderUnRecur (BinaryTree *root){
    cout<< "非递归先序遍历" << endl;
	BinaryTree *root1 = root;
    if (root1 != NULL)//排除头结点为空的情况
    {

		stack<BinaryTree *> stack;//建栈
		stack.push(root1);//压头结点
		while (!stack.empty())//如果栈不为空就弹栈
		{

			root1 = stack.top();
			stack.pop();
			cout << root1->data <<' ';//打印了头结点
			if (root1->right != NULL)
			{
				stack.push(root1->right);
			}
			if (root1-> left != NULL)
			{
				stack.push(root1->left);
			}//这里是右边先进栈但是后出栈
		}

		cout<< endl;

    }

}
//中序遍历非递归
void inOrderUnRecur (BinaryTree* root){
    cout<< "非递归中序遍历" << endl;
	BinaryTree *root1 = root;//建个指针对象指向根节点
	stack<BinaryTree*> stack2;//建个栈
    if (root1 != NULL)//如果根节点不为空的话
    {

		while ( !stack2.empty() || root1)//当栈不为空并且根节点不为空时
		{
			if (root1)//如果这个节点不为空就把他压栈并且去看看他的左节点(不停地把左边界进栈)
			{
				stack2.push(root1);
				root1 = root1->left;
			}
			else//左边界为空了就开始弹出节点
			{
                root1 = stack2.top();
				cout << root1->data << ' ';
				stack2.pop();//弹出节点并打印
				root1 = root1->right;//对右树周而复始压左树
			}

		}


    }
		cout << endl;
}
//前左再头的弄出来但是右树后干这件事

//后序遍历非递归
void postOrderUnRecur(BinaryTree * root){
 cout<< "非递归后序遍历" << endl;
		BinaryTree *root1 = root;
    if (root1 != NULL)
    {

		stack<BinaryTree *> stack,stack2;
		stack.push(root1);
		while (!stack.empty())
		{

			root1 = stack.top();
			stack.pop();
			stack2.push(root1);
			if (root1-> left != NULL)
			{
				stack.push(root1->left);
			}
			if (root1->right != NULL)
			{
				stack.push(root1->right);
			}

		}
		while (!stack2.empty())
		{
			cout << stack2.top()->data << " ";
			stack2.pop();
		}

		cout<< endl;

    }
}
int main()
{
	vector<char> path1, path2, path3;
	cout << "请使用前序遍历创建二叉树（若节点为空输入#代替）：" << endl;
	BinaryTree* root = NULL;
	CreatBinaryTree(root);
	BinaryTree* root_save = root;

	cout << "二叉树创建完成！" << endl;
	
	
	cout << "前序遍历二叉树结果为：" << endl;
	Preorder(root, path1);
	PrintBinaryTree(path1);
	preOrderUnRecur(root);

	cout << "中序遍历二叉树结果为：" << endl;
	Inorder(root, path2);
	PrintBinaryTree(path2);
	inOrderUnRecur(root);

	cout << "后序遍历二叉树结果为：" << endl;
	Postorder(root, path3);
	PrintBinaryTree(path3);
    postOrderUnRecur(root);

	system("pause");
	return 0;
}

相关leetcode题目：

在这里插入图片描述

前序遍历

144. 二叉树的前序遍历

/**
 * 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 preorder(vector<int>& res,TreeNode *root)
{
    if(root==NULL)
    {
        return;
    }
    res.push_back(root->val);
    preorder(res,root->left);
    preorder(res,root->right);
}
    vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;
    preorder(res,root);
    return res;
    }
    
};

非递归版：

/**
 * 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:

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

在这里插入图片描述

深度优先遍历：

257. 二叉树的所有路径

思路：二叉树的深度优先遍历

/**
 * 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:
    vector<string> binaryTreePaths(TreeNode* root) {
    vector<string> s;
    preorder(root,s,"");
    return s;
    }
    void preorder(TreeNode* root,vector<string> &s,string t)
    {
        t=t+to_string(root->val);
        if(!root->left&&!root->right)
        {
            s.push_back(t);
        }
       
        if(root->left)preorder(root->left,s,t+"->");
        if(root->right)preorder(root->right,s,t+"->");
        
    }
};

在这里插入图片描述

同为深度优先遍历的一个题:129. 求根节点到叶节点数字之和

  • 深度优先遍历记录一遍的数然后最后相加就可
/**
 * 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:
    int dfs(TreeNode* root, int prevSum) {
        if (root == nullptr) {
            return 0;
        }
        int sum = prevSum * 10 + root->val;
        if (root->left == nullptr && root->right == nullptr) {
            return sum;
        } else {
            return dfs(root->left, sum) + dfs(root->right, sum);
        }
    }
    int sumNumbers(TreeNode* root) {
        return dfs(root, 0);
    }
};

又深度优先遍历：剑指 Offer II 045. 二叉树最底层最左边的值

  • 深度优先遍历然后同时记录深度（前序遍历）先左后右然后达到最大深度时的第一个数就是二叉树最底层最左边的值
/**
 * 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:
int maxdepth=INT_MIN;
int data;
    int findBottomLeftValue(TreeNode* root) {
        
        dfs(root,0);
        return data;
    }
    void dfs(TreeNode* root,int depth)
    {
        if(!root)
        {
            return;
        }
        if(depth>maxdepth)
        {
            maxdepth=depth;
            data=root->val;
        }
        if(root->left)
        {
            dfs(root->left,depth+1);
        }
        
        if(root->right)
        {
            dfs(root->right,depth+1);
        }
    
    }
};

在这里插入图片描述

后序遍历

※ 后序遍历 剑指 Offer II 047. 二叉树剪枝

  • 后序遍历，要是这个为零然后左子树右子树都为空的时候就让这个节点为空，因为是后序遍历所以符合题目的情况。
/**
 - 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:
    TreeNode* pruneTree(TreeNode* root) {
        if(!root)return root;
        root->left=pruneTree(root->left);
        root->right=pruneTree(root->right);
        if(root->val==0&&!root->left&&!root->right)//从后向前遍历先看两子树如果都为0然后这个节点就为NULL就相当于删除了
        {
            return NULL;
        }
        return root;
    }
};

979. 在二叉树中分配硬币(后序,较难)

思路：首先我们要让每个节点都为1；我们可以让根节点来分这个东西总体来说就是让每个叶子的钱交给他的根节点来分配，而这样的分配方式最重要的就是后序遍历

  • 节点的数>=1,他多了就把这个节点给他的父亲(儿子剩余的钱当然要给父亲)；
  • 节点的数为0，他少了的可以从他的兄弟那可以拿，也可以从他的父亲那拿；
  • 如何实现呢？我们把两个孩子的钱统一一下给父亲交上去 sum+=(abs(l)+abs®);
  • 而这个l 和 r就是这个节点加上他的儿子交的钱减去自己留的1块钱别的全交给他的父亲
/**
 * 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:
int sum;
    int distributeCoins(TreeNode* root) {
        sum=0;
        dfs(root);
        return sum;
    }
    int dfs(TreeNode* root)
    {
        if(!root)return 0;
        int l=dfs(root->left);
        int r=dfs(root->right);
        sum+=(abs(l)+abs(r));
        return root->val+l+r-1;
    }
};

在这里插入图片描述

层序遍历

二叉树的层序遍历 102. 二叉树的层序遍历

二叉树的深度遍历都会了那么二叉树的层序遍历怎么搞呢
首先可以使用我们前面已经可以熟练使用的dfs
这里注意使用dfs的时候要用depth+1而不能用depth++

DFS做法：

/**
 - 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:
    vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> result;
    dfs(result,root,0);
    return result;
    }
    void dfs(vector<vector<int>> &result,TreeNode *root,int depth)
    {
        if(!root)return;
        if(depth>=result.size())
        {
            result.push_back(vector<int>{});
        }
        result[depth].push_back(root->val);
        dfs(result,root->left,depth+1);//注意这里不能用depth++,要用depth+1
        dfs(result,root->right,depth+1);

    }
};

在这里插入图片描述

BFS做法（广度优先搜索）：

广度优先搜索的话就要用到我们的老朋友堆栈了,别看他有个特殊的名字其实还是很简单的
我们可以用一种巧妙的方法修改广度优先搜索：

  • 就是申请一个队列一个vector
  • 先把根节点压进去
  • 搞个如果队列为空及break的循环
    • 循环内每循环一次vector中增加一个vector表示增加一个深度
    • 记录队列长度把所有的队列中的节点的值都出队到新的vector中
    • 如果这个节点有左右孩子就把他左右孩子压进去（下一个层了）
      注意要考虑root==NULL的情况

代码：

/**
 * 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:
    vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>>res;
    queue<TreeNode*>q1;
    if(!root)
    {
        return res;
    }
    q1.push(root);
    while(!q1.empty())
    {
        int length=q1.size();
        res.push_back(vector<int>{});//新建一个数组表示又有一层
        for(int i=0;i<length;i++)
        {
            TreeNode* index=q1.front();q1.pop();
            res.back().push_back(index->val);
            if(index->left)q1.push(index->left);
            if(index->right)q1.push(index->right);
        }
    }   
      return res;     
    }
   
};

107. 二叉树的层序遍历 II

妈耶别说了缝缝补补又三年

/**
 * 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:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
   vector<vector<int>>res;
    queue<TreeNode*>q1;
    if(!root)
    {
        return res;
    }
    q1.push(root);
    while(!q1.empty())
    {
        int length=q1.size();
        res.insert(res.begin(),vector<int>{});//新建一个数组表示又有一层
        for(int i=0;i<length;i++)
        {
            TreeNode* index=q1.front();q1.pop();
            res.front().push_back(index->val);
            if(index->left)q1.push(index->left);
            if(index->right)q1.push(index->right);
        }
    }   
      return res;     
    }
    
};

在这里插入图片描述

剑指 Offer II 046. 二叉树的右侧视图 （199. 二叉树的右视图）

上上个题BFS记录队列的最后一个值

/**
 * 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:
    vector<int> rightSideView(TreeNode* root) {
    vector<int> res;
    queue<TreeNode*>q1;
    if(!root)
    {
        return res;
    }
    q1.push(root);
    while(!q1.empty())
    {
        int length=q1.size();

        for(int i=0;i<length;i++)
        {
            TreeNode* index=q1.front();q1.pop();
            if(i==length-1)
            {
                res.push_back(index->val);
            }
            if(index->left)q1.push(index->left);
            if(index->right)q1.push(index->right);
        }
    
    }
return res;
    }
};

在这里插入图片描述

二叉树的插入

919. 完全二叉树插入器

二叉树的构造

105. 从前序与中序遍历序列构造二叉树

这个的思路就是，前序遍历的第一个节点肯定是根节点的话这个节点的左树就是中序遍历中的和这个点相同的那个值的左边的那些，右树就是右面的那些。
1.添加前序遍历的第一个
2.中序遍历中找到与前序遍历的第一个相同的值记录下位置
3.递归构建左子树和右子树

/**
 * 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:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return preBuildTree(0,preorder.size()-1,0,inorder.size()-1,preorder,inorder);
    }
    TreeNode *preBuildTree(int preleft,int preright,int inleft,int inright,vector<int>& preorder, vector<int>& inorder)
    {
        if(preleft>preright||inleft>inright)
        {
            return NULL;
        }
        int val=preorder[preleft];
        int inp=inleft;
        while(inp<=inright&&inorder[inp]!=val)
        {
              inp++;
        }
        TreeNode *tree = new TreeNode(val);
        int left=inp-inleft;
        tree->left=preBuildTree(preleft+1,preleft+left,inleft,inp-1,preorder,inorder);
        tree->right=preBuildTree(preleft+left+1,preright,inp+1,inright,preorder,inorder);
        return tree;
        }
};

在这里插入图片描述
好了上个题会做了的话我们直接做一下下一个题吧建议自己写基本一模一样的。

/**
 * 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:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return buildingTree(0,inorder.size()-1,0,postorder.size()-1,inorder,postorder);
    }
    TreeNode* buildingTree(int postleft,int postright,int inleft,int inright,vector<int>& inorder, vector<int>& postorder)
{
    if(inleft>inright||postleft>postright)return NULL;
    TreeNode* tree = new TreeNode(postorder[postright]);
    int inroot = inleft;
    while(inroot<=inright&&inorder[inroot]!=postorder[postright])
    {
        inroot++;
    }
    int left= inroot-inleft;
    tree->left=buildingTree(postleft,postleft+left-1,inleft,inroot-1,inorder,postorder);
    tree->right=buildingTree(postleft+left,postright-1,inroot+1,inright,inorder,postorder);
    return tree;
}
};

这种题的根本思路就是根据inorder来确认前序或者后序遍历中的左子树右子树的范围然后递归解决就可以了，每次递归根节点都向前移动一个前序是+1后序是－1；

449. 序列化和反序列化二叉搜索树

二叉搜索树，由于各元素之间有左子节点小于父节点再小于右子节点的性质，因此用一个前序排列就可以确定出唯一结构

因为二叉搜索树的左子树节点都小于根节点而右节点都大于根节点，所以经过排序以后就可以确认这个二叉树的中序遍历然后我们就可以进行上上一个题的操作了~

class Codec {
public:
	string serialize(TreeNode* root) {  //确定一个前序序列，这个不解释了
		if (!root)	return "";
		stack<TreeNode*> st;
		TreeNode* temp = root;
		string res;
		while (temp || !st.empty()) {
			while (temp) {
				res += (to_string(temp->val) + ' ');
				st.push(temp);
				temp = temp->left;
			}
			if (!st.empty()) {
				temp = st.top()->right;
				st.pop();
			}
			else
				temp = nullptr;
		}
		return res;
	}

	TreeNode* deserialize(string data) {  
		int slen = data.size(), temploc = 0;
		vector<TreeNode*> nums; 
		while (temploc != slen) {  
			int tempnum = 0;
			while (data[temploc] != ' ')
				tempnum = tempnum * 10 + data[temploc++] - '0';
			nums.push_back(new TreeNode(tempnum));
			++temploc;
		}
		
		TreeNode* head = new TreeNode(INT_MAX); 
		stack<TreeNode*> st;
		st.push(head);
		int loc = 0, len = nums.size();
		while (loc != len) {
			if (nums[loc]->val < st.top()->val) {
				st.top()->left = nums[loc];
				st.push(nums[loc]);
				++loc;
			}
			else {
				TreeNode* temp = st.top();
				st.pop();
				while (nums[loc]->val > st.top()->val) {
					temp = st.top();
					st.pop();
				}
				temp->right = nums[loc];
				st.push(nums[loc]);
				++loc;
			}
		}
		return head->left;
	}
};

在这里插入图片描述

LCA最近公共祖先

二叉搜索树版

首先从根节点开始找起；

  • 如果两个结点的值一个比根节点（当前查找的结点）的值小，另一个比根节的值点大，则根节点就是两个指定节点的最近公共祖先。（递归出口）
  • 如果两个结点的值都比根节点（当前查找的结点）的值小，则直接在该节点的左子树上寻找。
  • 如果两个结点的值都比根节点（当前查找的结点）的值大，则直接在该节点的右子树上寻找。
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root)
        {
            return NULL;
        }
        if((p->val>=root->val&&q->val<=root->val)||(p->val<=root->val&&q->val>=root->val))
        {
            return root;
        }
        else if(p->val>root->val&&q->val>root->val)
        {
            return lowestCommonAncestor(root->right,  p, q);//都大就去大的那边去找
        }
        else
        {
            return lowestCommonAncestor(root->left, p,  q);//都小就去小的那边去找
        }
    }
};

这种二叉搜索树的还是比较简单的那要是不是二叉搜索树怎么办呢？

LCA非二叉树版:

1.终止条件：
1.当越过叶节点，则直接返回 nullnull ；
2.当 rootroot 等于 p, qp,q ，则直接返回 rootroot ；
2.递归工作：
1.开启递归左子节点，返回值记为 leftleft ；
2.开启递归右子节点，返回值记为 rightright ；
3.返回值： 根据 leftleft 和 rightright ，可展开为四种情况；
1.当 leftleft 和 rightright 同时为空 ：说明 rootroot 的左 / 右子树中都不包含 p,qp,q ，返回 nullnull ；
2.当 leftleft 和 rightright 同时不为空 ：说明 p, qp,q 分列在 rootroot 的 异侧 （分别在 左 / 右子树），因此 rootroot 为最近 公共祖先，返回 rootroot ；
3.当 leftleft 为空 ，rightright 不为空 ：p,qp,q 都不在 rootroot 的左子树中，直接返回 rightright 。具体可分为两种情况：
1.p,qp,q 其中一个在 rootroot 的 右子树 中，此时 rightright 指向 pp（假设为 pp ）；
2.p,qp,q 两节点都在 rootroot 的 右子树 中，此时的 rightright 指向 最近公共祖先节点 ；
4.当 leftleft 不为空 ， rightright 为空 ：与情况 3. 同理；

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root||root==p||root==q)return root;//如果为空或者是找到了p或者是q就直接返回可=了，不然就错过了p和q了。
        TreeNode*left=lowestCommonAncestor(root->left,p,q);//用left储存向左找得结果
        TreeNode*right=lowestCommonAncestor(root->right,p,q);//用right储存向右找得结果
        if(!left)return right;//左子树找不到就返回右子树
        if(!right)return left;//右子树找不到就返回左子树
        return root;//都找到了就是root为公共的祖先
    }
};

​​在这里插入图片描述

Love is worth years.❤
热爱可抵岁月漫长。
​​​​
本文部分思路来源于网络如有侵权联系删除~

相关文章：

  • 软件企业和双软企业的区别
  • 字节跳动安全Ai挑战赛-基于文本和多模态数据的风险识别总结
  • DRF-(10)
  • java面试-GC垃圾回收机制
  • TOREX | 如何延长设备的电池寿命？——充电IC
  • 电路方案分析（十一）低电平（5uA）V-I转化器
  • 【Hadoop生态圈】8.Flink入门教程
  • 代码整洁之道，评审问题分享记录
  • 【调研】详解Transformer结构——Attention Is All You Need
  • Linux基础组件之消息协议设计概述
  • [ vulhub漏洞复现篇 ] struts2远程代码执行漏洞 S2-005 （CVE-2010-1870）
  • 微服务Spring Boot 整合 Redis 分布式锁 Redission 实现优惠卷秒杀 一人一单
  • java毕业设计医护人员排班系统Mybatis+系统+数据库+调试部署
  • 分库分表实战之从根上带你吃透MySQL的索引
  • 学习大数据环境搭建
  • 「前端」从UglifyJSPlugin强制开启css压缩探究webpack插件运行机制
  • angular2 简述
  • css系列之关于字体的事
  •  D - 粉碎叛乱F - 其他起义
  • Elasticsearch 参考指南（升级前重新索引）
  • GraphQL学习过程应该是这样的
  • hadoop入门学习教程--DKHadoop完整安装步骤
  • laravel with 查询列表限制条数
  • PHP 7 修改了什么呢 -- 2
  • Python十分钟制作属于你自己的个性logo
  • RxJS 实现摩斯密码(Morse) 【内附脑图】
  • 第三十一到第三十三天：我是精明的小卖家（一）
  • 湖南卫视：中国白领因网络偷菜成当代最寂寞的人?
  • 前端性能优化——回流与重绘
  • 删除表内多余的重复数据
  • 设计模式 开闭原则
  • 深入浅出Node.js
  • 深入浅出webpack学习(1)--核心概念
  • 吐槽Javascript系列二：数组中的splice和slice方法
  • 正则学习笔记
  • 自动记录MySQL慢查询快照脚本
  • 深度学习之轻量级神经网络在TWS蓝牙音频处理器上的部署
  • JavaScript 新语法详解：Class 的私有属性与私有方法 ...
  • 湖北分布式智能数据采集方法有哪些？
  • 选择阿里云数据库HBase版十大理由
  • # 安徽锐锋科技IDMS系统简介
  • #单片机（TB6600驱动42步进电机）
  • #我与Java虚拟机的故事#连载14：挑战高薪面试必看
  • $redis-setphp_redis Set命令，php操作Redis Set函数介绍
  • （1）STL算法之遍历容器
  • （ISPRS，2023）深度语义-视觉对齐用于zero-shot遥感图像场景分类
  • (欧拉)openEuler系统添加网卡文件配置流程、(欧拉)openEuler系统手动配置ipv6地址流程、(欧拉)openEuler系统网络管理说明
  • (转）【Ｈibernate总结系列】使用举例
  • (转)Google的Objective-C编码规范
  • （转）机器学习的数学基础（1）--Dirichlet分布
  • (自适应手机端)响应式新闻博客知识类pbootcms网站模板 自媒体运营博客网站源码下载
  • .NET C# 使用 SetWindowsHookEx 监听鼠标或键盘消息以及此方法的坑
  • .NET MVC第三章、三种传值方式
  • .NET MVC第五章、模型绑定获取表单数据
  • .NET Standard 的管理策略