1. Toy模板网首页
  2. > Toy博客

[C++随想录] 二叉搜索树

10月前 作者：雨 子 分类：Toy博客 阅读(37) 违法举报

这篇具有很好参考价值的文章主要介绍了[C++随想录] 二叉搜索树。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

二叉搜索树的使用

二叉搜索树 相较于 普通的二叉树来说:

  1. 根节点的左子树的所有键值都 小于 根节点, 根节点的右子树的所有键值 大于 根节点
  2. 根节点的 左右子树 都是 二叉搜索树
  3. 中序遍历 是 升序的 ⇒ 二叉搜素树 又叫作 二叉排序树
  • 子树 && 节点
    [C++随想录] 二叉搜索树,C++,c++,算法,开发语言,stl
  1. 查找
    假如查找 key, 有如下 四种情况:
    1. 如果 key > 根节点的值, 那么就去根节点的右子树去查找
    2. 如果 key <根节点的值, 那么就去根节点的左子树去查找
    3. 如果 key = 根节点的值, 那么就找到了
    4. 如果找到 空, 那就不存在
  • 查找的时间复杂度是 O(高度次), 而不是 O(logN)
    如果是 完全二叉树, 那么就是 O(logN); 如果 退化到极限情况, 类似于链表, 那么就是 O(N)
    [C++随想录] 二叉搜索树,C++,c++,算法,开发语言,stl
    所以, 总结下来, 时间复杂度就是 O(高度次)
    那么如何解决这种 退化问题呢? ⇒ AVL树 和 红黑树 就是针对这种情况做了特殊处理 --> 旋转

  1. 插入
    总体思想: 找到非空节点去插入
    [C++随想录] 二叉搜索树,C++,c++,算法,开发语言,stl

  2. 删除key

    1. 先找到key的位置, 有两种情况:
      1. 没找到, 那就直接返回
      2. 找到了key的位置, 记作cur. 找到了也有三种情况:
        1. cur的左子树为空
        2. cur的右子树为空
        3. cur的左右子树都不为空

由于 cur要进行删除, 要把cur后面的内容链接到parent的后面. && cur也有两种可能 parent的左子树 or 右子树 ⇒ 我们要cur后面的内容链接到 cur处于parent的位置
删除具体如下👇👇👇

  1. cur的右子树为空
    (1) cur是parent的左子树
    [C++随想录] 二叉搜索树,C++,c++,算法,开发语言,stl
    (2) cur是parent的右子树
    [C++随想录] 二叉搜索树,C++,c++,算法,开发语言,stl
  2. cur的左子树为空
    (1) cur是parent的左子树
    [C++随想录] 二叉搜索树,C++,c++,算法,开发语言,stl
    (2) cur是parent的右子树
    [C++随想录] 二叉搜索树,C++,c++,算法,开发语言,stl
  3. cur的左右子树都不为空
    🗨️删除掉cur, 那么我们如何链接cur的左右子树呢?
    • 可以找一个节点来替换掉cur, 然后我们来处理这个节点的链接关系就好了
      🗨️替换过去, 也不改变二叉搜索树的结构, 那么节点是什么好呢? 后面集中处理这个节点, 那么这个节点应该容易处理才对, 那么这个节点是叶子节点吗?
    • 替换过去, 不改变二叉树的结构 — — 替换节点应该为 cur的左子树的最大节点 或者 cur的右子树的最小节点 ⇐ 中序遍历, cur旁边的两个数; 中序是 左跟右, ⇒ 那么就应该是左子树的最大节点, 或者右子树的最小节点
      左子树的最大节点, 或者右子树的最小节点; 正好是叶子节点 ⇒ 那么我们处理这个替换节点也比较 容易 ⇒ 思想同上 替换节点的左子树为空, 或 替换节点的右子树为空
      [C++随想录] 二叉搜索树,C++,c++,算法,开发语言,stl

二叉搜索树的模拟实现(K)

整体结构

[C++随想录] 二叉搜索树,C++,c++,算法,开发语言,stl
Node类

	template<class T>
	struct BSTreeNode
	{
	public:
		BSTreeNode(const T& key)
			:_left(nullptr)
			,_right(nullptr)
			,_key(key)
		{}

	public:
		BSTreeNode<T>* _left;
		BSTreeNode<T>* _right;
		T _key;
	};

BSTree类

template<class T>
class BSTree
{
	typedef BSTreeNode<T> Node;
public:
	BSTree()
		:_root(nullptr)
	{}
	
	// 析构函数
	~BSTree()
	{
		_BSTree(_root);
	}
	
private:
		// 析构函数
		void _BSTree(Node* root)
		{
			if (root == nullptr)
				return;

			// 后序遍历进行删除
			_BSTree(root->_left);
			_BSTree(root->_right);
			delete root;
		}
		
	// 成员函数
	Node* _root;
}

循环版本

  1. find
Node* find(const K& key)
{
	return _find(_root, key);
}

private:
Node* _find(Node* root, const T& key)
{
	Node* cur = root;

	while (cur)
	{
		if (key > cur->_key)
		{
			cur = cur->_right;
		}
		else if (key < cur->_key)
		{
			cur = cur->_left;
		}
		else
		{
			return cur;
		}
	}

	return nullptr;
}
  1. insert
bool insert(const T& key)
{
	Node* newnode = new Node(key);

	if (_root == nullptr)
	{
		_root = newnode;
		return true;
	}

	Node* parent = nullptr;
	Node* cur = _root;
	// 寻找插入的位置
	while (cur)
	{
		if (key > cur->_key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (key < cur->_key)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			break;
		}
	}

	// 链接
	if (key > parent->_key)
	{
		parent->_right = newnode;
	}
	else if (key < parent->_key)
	{
		parent->_left = newnode;
	}
	else
	{
		return false;
	}

	return true;
}
  1. inorder
void Inorder()
{
	_Inorder(_root);
}

private:
void _Inorder(Node* root)
{
	if (root == nullptr)
		return;

	_Inorder(root->_left);
	std::cout << root->_key << " ";
	_Inorder(root->_right);

}
  1. erase
    [C++随想录] 二叉搜索树,C++,c++,算法,开发语言,stl
    [C++随想录] 二叉搜索树,C++,c++,算法,开发语言,stl 
bool erase(const T& key)
{
	return _erase(_root, key);
}

private:
bool _erase(Node* root, const T& key)
{
	// 先找到位置
	Node* parent = root;
	Node* cur = root;

	while (cur)
	{
		if (key > cur->_key)
		{
			parent = cur;
			cur = cur->_right;

		}	
		else if (key < cur->_key)
		{
			parent = cur;
			cur = cur->_left;
		}
		// 找到了
		else
		{
			// 左为空
			if (cur->_left == nullptr)
			{
				
				if (cur == _root)
				{
					_root = cur->_right;
				}
				else
				{
					// 判读cur是parent的位置
					if (cur == parent->_left)
					{
						parent->_left = cur->_right;
					}
					else if (cur == parent->_right)
					{
						parent->_right = cur->_right;
					}
				}
			}
			// 右为空
			else if (cur->_right == nullptr)
			{
				if (cur == _root)
				{
					_root = cur->_left;
				}
				else
				{
					// 判读cur是parent的位置
					if (cur == parent->_left)
					{
						parent->_left = cur->_left;
					}
					else if (cur == parent->_right)
					{
						parent->_right = cur->_left;
					}
				}
			}
			// 左右都不为空
			else
			{
				// 先找到cur的左子树的最大值 或 右子树的最小值
				// parent必须初始化为cur -- 以防删除的就是头节点
				Node* parent = cur;
				Node* LeftMax = cur->_left;
				while (LeftMax->_right)
				{
					parent = LeftMax;
					LeftMax = LeftMax->_right;
				}

				// 交换cur 和 LeftMax的值
				std::swap(cur->_key, LeftMax->_key);

				// 改变链接关系
				if (parent->_left == LeftMax)
				{
					parent->_left = LeftMax->_left;
				}
				else if (parent->_right == LeftMax)
				{
					parent->_right = LeftMax->_left;
				}

				cur = LeftMax;
			}
			
			// 集中释放 cur
			delete cur;
			return true;
		}
	}

	return false;
}

递归版本

  1. findr
    无需链接关系 — — 不用引用即可
    1. 递归退出条件 root == nullptr, 那就返回nullptr
    2. 根据二叉搜索数的特性: 大了往右边走, 小了往左边走, 相等就返回当前节点的指针;
Node* findr(const T& key)
{
	return _findr(_root, key);
}

private:
Node*_findr(Node* root, const T& key)
{
	if (root == nullptr)
		return nullptr;

	if (key < root->_key)
	{
		_findr(root->_left, key);
	}
	else if (key > root->_key)
	{
		_findr(root->_right, key);
	}
	else
	{
		return root;
	}
}
  1. insertr
    需要重新链接 -- -- 引用的妙用
    总体思想 : 遇到空就插入
    1. 递归返回条件 : 遇到空, 插入后, 返回true
    2. 二叉树的特性: 大了往右边走, 小了往左边走, 相等返回false
      [C++随想录] 二叉搜索树,C++,c++,算法,开发语言,stl
      [C++随想录] 二叉搜索树,C++,c++,算法,开发语言,stl 
bool insertr(const T& key)
{
	return _insertr(_root, key);
}

private:
bool _insertr(Node*& root, const T& key)
{
	if (root == nullptr)
	{
		root = new Node(key);
		return true;
	}

	if (key > root->_key)
	{
		return _insertr(root->_right, key);
	}
	else if (key < root->_key)
	{
		return _insertr(root->_left, key);
	}
	else
	{
		return false;
	}
}
  1. eraser
    需要重新链接 -- -- 引用的妙用
    1. 递归结束条件: 遇到空就返回 false
    2. 先找到位置, 记作 cur
    3. cur有三种情况 :cur的左子树为空, cur的右子树为空, cur的左右子树都不为空; 三种情况分类讨论

这个和上面的 引用的妙用是一样的道理, 那么我就不在这里画 递归展开图

bool eraser(const T& key)
{
	return _eraser(_root, key);
}

private:
bool _eraser(Node*& root, const T& key)
{
	if (root == nullptr)
	{
		return false;
	}

	if (key > root->_key)
	{
		_eraser(root->_right, key);
	}
	else if (key < root->_key)
	{
		_eraser(root->_left, key);
	}
	else
	{
		// 由于是上面节点的引用 && 要删掉root节点
		// ⇒ 找一个背锅侠来代替root节点去删除
		Node* tem = root;
		
		// 左子树为空
		if (root->_left == nullptr)
		{
			root = root->_right;
		}
		//右子树为空
		else if (root->_right == nullptr)
		{
			root = root->_left;
		}
		// 左右子树都不为空
		else
		{
			// 找到左树的最大节点
			Node* maxleft = root->_left;
			while (maxleft->_right)
			{
				maxleft = maxleft->_right;
			}
			
			// 交换root 和 maxleft的值
			std::swap(maxleft->_key, root->_key);
			
			// 重新链接
			root = maxleft->_left;
			
			// 背锅侠就位
			tem = maxleft;
		}
		
		// 统一删除
		delete tem;
		return true;
	}

	return false;
}

二叉搜索树的应用

二叉搜索树主要有两个版本 K版本 和 KV版本
KV版本 相较于 K版本 就多了个 value
[C++随想录] 二叉搜索树,C++,c++,算法,开发语言,stl

template<class K, class V>
	struct BSTreeNode
	{
	public:
		BSTreeNode(const K& key, const V& value)
			:_left(nullptr)
			,_right(nullptr)
			,_key(key)
			,_value(value)
		{}

	public:
		BSTreeNode<K,V>* _left;
		BSTreeNode<K,V>* _right;
		K _key;
		V _value;
	};

template<class K, class V>
class BSTree
{
	typedef BSTreeNode<K, V> Node;
public:
	BSTree()
		:_root(nullptr)
	{}
private:
	Node* _root;
}

由于 还是对 K 进行操作 ⇒ 我们这里就不写 KV的代码了. 后面源码会附上 KV的完整代码

二叉搜索树主要应用于两种模型: K模型 和 KV模型

  1. K模型 — — 根据关键码Key去解决 在不在的问题
    比如 : 判断单词是否拼写错误 (将词库导入二叉搜索树, 然后判断在不在)
void test1()
{
	// 模拟导入词库
	muyu::BSTree<string, string> World;
	World.insert("insert", "插入");
	World.insert("input", "输入");
	World.insert("output", "输出");
	World.insert("love", "爱情");

	string str;
	while (cin >> str)
	{
		// 查找是否在词库中出现
		auto ret = World.find(str);
		if (ret)
		{
			cout << "输入正确" << endl;
		}
		else
		{
			cout << "查无单词, 请重新输入" << endl;
		}
	}
}

int main()
{
	test1();

	return 0;
}

运行结果:
[C++随想录] 二叉搜索树,C++,c++,算法,开发语言,stl

  1. KV模型 — — 每一个关键码Key, 都有一个与之对应的 Value, 存在 <Key, Value>键值对
    比如: 统计水果出现的次数
void test2()
{
	muyu::BSTree<string, int> cnt;
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" };

	for (const auto& e : arr)
	{
		auto res = cnt.find(e);
		// 第一次插入, 次数就给个1
		if (!res)
		{
			cnt.insert(e, 1);
		}
		// 不是第一次插入, 就在key对应的value进行++
		else
		{
			res->_value++;
		}

	}

	cnt.Inorder();
}

int main()
{
	test2();

	return 0;
}

运行结果:

苹果 6
西瓜 3
香蕉 2

源码(kv)

#pragma once

namespace muyu
{
	template<class K, class V>
	struct BSTreeNode
	{
	public:
		BSTreeNode(const K& key = K(), const V& value = V())
			:_left(nullptr)
			,_right(nullptr)
			,_key(key)
			,_value(value)
		{}

	public:
		BSTreeNode<K,V>* _left;
		BSTreeNode<K,V>* _right;
		K _key;
		V _value;
	};

	template<class K, class V>
	class BSTree
	{
		typedef BSTreeNode<K, V> Node;
	public:
		BSTree()
			:_root(nullptr)
		{}

		~BSTree()
		{
			_BSTree(_root);
		}

		bool insert(const K& key, const V& value)
		{
			Node* newnode = new Node(key, value);

			if (_root == nullptr)
			{
				_root = newnode;
				return true;
			}

			Node* parent = nullptr;
			Node* cur = _root;
			// 寻找插入的位置
			while (cur)
			{
				if (key > cur->_key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (key < cur->_key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					break;
				}
			}

			// 链接
			if (key > parent->_key)
			{
				parent->_right = newnode;
			}
			else if (key < parent->_key)
			{
				parent->_left = newnode;
			}
			else
			{
				return false;
			}

			return true;
		}

		bool insertr(const K& key)
		{
			return _insertr(_root, key);
		}

		void Inorder()
		{
			_Inorder(_root);
		}

		Node* find(const K& key)
		{
			return _find(_root, key);
		}

		Node* findr(const K& key)
		{
			return _findr(_root, key);
		}

		bool erase(const K& key)
		{
			return _erase(_root, key);
		}

		bool eraser(const K& key)
		{
			return _eraser(_root, key);
		}

	private:

		void _BSTree(Node* root)
		{
			if (root == nullptr)
				return;

			// 后序遍历进行删除
			_BSTree(root->_left);
			_BSTree(root->_right);
			delete root;
		}

		void _Inorder(Node* root)
		{
			if (root == nullptr)
				return;

			_Inorder(root->_left);
			std::cout << root->_key << " " << root->_value << std::endl;
			_Inorder(root->_right);

		}

		Node* _insertr(Node*& root, const K& key, const V& value)
		{
			if (root == nullptr)
			{
				root = new Node(key, value);
				return root;
			}

			if (key > root->_key)
			{
				return _insertr(root->_right, key);
			}
			else if (key < root->_key)
			{
				return _insertr(root->_left, key);
			}
			else
			{
				return nullptr;
			}
		}

		Node* _find(Node* root, const K& key)
		{
			Node* cur = root;

			while (cur)
			{
				if (key > cur->_key)
				{
					cur = cur->_right;
				}
				else if (key < cur->_key)
				{
					cur = cur->_left;
				}
				else
				{
					return cur;
				}
			}

			return nullptr;
		}

		Node* _findr(Node* root, const K& key)
		{
			if (root == nullptr)
				return nullptr;

			if (key < root->_key)
			{
				_findr(root->_left, key);
			}
			else if (key > root->_key)
			{
				_findr(root->_right, key);
			}
			else
			{
				return root;
			}
		}

		bool _erase(Node* root, const K& key)
		{
			// 先找到位置
			Node* parent = root;
			Node* cur = root;

			while (cur)
			{
				if (key > cur->_key)
				{
					parent = cur;
					cur = cur->_right;

				}	
				else if (key < cur->_key)
				{
					parent = cur;
					cur = cur->_left;
				}
				// 找到了
				else
				{
					// 左为空
					if (cur->_left == nullptr)
					{
						
						if (cur == _root)
						{
							_root = cur->_right;
						}
						else
						{
							// 判读cur是parent的位置
							if (cur == parent->_left)
							{
								parent->_left = cur->_right;
							}
							else if (cur == parent->_right)
							{
								parent->_right = cur->_right;
							}
						}
					}
					// 右为空
					else if (cur->_right == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_left;
						}
						else
						{
							// 判读cur是parent的位置
							if (cur == parent->_left)
							{
								parent->_left = cur->_left;
							}
							else if (cur == parent->_right)
							{
								parent->_right = cur->_left;
							}
						}
					}
					// 左右都不为空
					else
					{
						// 先找到cur的左子树的最大值 或 右子树的最小值
						Node* parent = cur;
						Node* LeftMax = cur->_left;
						while (LeftMax->_right)
						{
							parent = LeftMax;
							LeftMax = LeftMax->_right;
						}

						// 交换cur 和 LeftMax的值
						std::swap(cur->_key, LeftMax->_key);

						// 改变链接关系
						if (parent->_left == LeftMax)
						{
							parent->_left = LeftMax->_left;
						}
						else if (parent->_right == LeftMax)
						{
							parent->_right = LeftMax->_left;
						}

						cur = LeftMax;
					}

					delete cur;
					return true;
				}
			}

			return false;
		}

		bool _eraser(Node*& root, const K& key)
		{
			if (root == nullptr)
			{
				return false;
			}

			if (key > root->_key)
			{
				_eraser(root->_right, key);
			}
			else if (key < root->_key)
			{
				_eraser(root->_left, key);
			}
			else
			{
				Node* tem = root;

				if (root->_left == nullptr)
				{
					root = root->_right;
				}
				else if (root->_right == nullptr)
				{
					root = root->_left;
				}
				else
				{
					Node* maxleft = root->_left;
					while (maxleft->_right)
					{
						maxleft = maxleft->_right;
					}

					std::swap(maxleft->_key, root->_key);

					root = maxleft->_left;

					tem = maxleft;
				}

				delete tem;
				return true;
			}

			return false;
		}

		Node* _root;
	};
}

晚日寒鸦一片愁。柳塘新绿却温柔。若教眼底无离恨，不信人间有白头。
肠已断，泪难收。相思重上小红楼。情知已被山遮断，频倚阑干不自由。
— — 辛弃疾· 《鹧鸪天》文章来源地址https://www.toymoban.com/news/detail-736285.html

到了这里，关于[C++随想录] 二叉搜索树的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 代码随想录二刷day22 |二叉树之 235. 二叉搜索树的最近公共祖先 701.二叉搜索树中的插入操作 450.删除二叉搜索树中的节点

    235. 二叉搜索树的最近公共祖先 题目链接 解题思路：讨论 中节点 p 中节点 q 或者 中节点 q 中节点 p ，其余的情况的最近公共祖先就是根节点。 使用递归三部曲 确定递归函数返回值以及参数 参数就是当前节点，以及两个结点 p、q。 返回值是要返回最近公共祖先，所以是Tr

    2024年02月08日
    浏览(49)
  • [代码随想录]二叉树

    [代码随想录]二叉树

    二叉树可以链式存储，也可以顺序存储。 那么链式存储方式就用指针， 顺序存储的方式就是用数组。 顾名思义就是顺序存储的元素在内存是连续分布的，而链式存储则是通过指针把分布在各个地址的节点串联一起。 链式存储如图： 链式存储是大家很熟悉的一种方式，那么

    2024年02月03日
    浏览(59)
  • 代码随想录笔记--二叉树篇

    代码随想录笔记--二叉树篇

    目录 1--递归遍历 1-1--前序遍历 1-2--中序遍历 1-3--后序遍历 2--迭代遍历 2-1--前序遍历 2-2--后序遍历 2-3--中序遍历 3--二叉树的层序遍历 4--翻转二叉树 5--对称二叉树 6--二叉树最大深度 7--二叉树的最小深度 8--完全二叉树节点的数量 9--平衡二叉树 10--二叉树的所有路径 11--左叶子之

    2024年02月10日
    浏览(49)
  • 代码随想录 二叉树 Java（二）

    代码随想录 二叉树 Java（二）

    采用前序遍历的方式遍历该二叉树，然后统计该二叉树的节点个数 这种方式比较简单，但是没有利用题目中所给的完全二叉树这一信息 官方思路：二分查找+位运算 对于任意二叉树，都可以通过广度优先搜索或深度优先搜索计算节点个数，时间复杂度和空间复杂度都是O(n)，

    2024年02月08日
    浏览(51)
  • 跟着《代码随想录刷题》（六）—— 二叉树

    跟着《代码随想录刷题》（六）—— 二叉树

    LeetCode：114、二叉树的前序遍历 （1）递归法 （2）迭代法 （3）统一迭代格式 LeetCode：94、二叉树的中序遍历 （1）递归法 （2）迭代法 （3）统一迭代格式 LeetCode：145、二叉树的后序遍历 （1）递归法 （2）迭代法 （3）统一迭代格式 LeetCode：589、N叉树前序遍历 LeetCode：590、N叉

    2024年02月09日
    浏览(47)
  • 代码随想录二刷 ｜二叉树 ｜ 二叉树的右视图

    代码随想录二刷 ｜二叉树 ｜ 二叉树的右视图

    199.二叉树的右视图 给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。 示例 1: 输入: [1,2,3,null,5,null,4] 输出: [1,3,4] 示例 2: 输入: [1,null,3] 输出: [1,3] 示例 3: 输入: [] 输出: [] 提示: 二叉树的节点个数的范围是 [0,1

    2024年02月04日
    浏览(61)
  • 1月3日代码随想录反转二叉树

    1月3日代码随想录反转二叉树

    给你一棵二叉树的根节点  root  ，翻转这棵二叉树，并返回其根节点。 示例 1： 示例 2： 示例 3： 提示： 树中节点数目范围在  [0, 100]  内 -100 = Node.val = 100 这道题用递归的思想就是将根节点的左右儿子交换，然后再对子节点进行递归操作，直到子节点均为空。 但是我感觉

    2024年02月03日
    浏览(47)
  • 代码随想录day13 | 226.翻转二叉树 101.对称二叉树

    代码随想录day13 | 226.翻转二叉树 101.对称二叉树

    使用前、后序反转最为方便。 为啥不推荐中序？ 中序遍历，某些节点的左右孩子会翻转两次，某些节点左右孩子不会被反转。 101.对称二叉树 关键在于，看这个节点对应的左子树和右子树是否可以相互反转。 1、如何比较呢？ 比较的是两个子树的里侧和外侧的元素是否相等

    2024年02月15日
    浏览(39)
  • 【Day22-慢就是快】代码随想录-二叉树-迭代遍历

    【Day22-慢就是快】代码随想录-二叉树-迭代遍历

    用迭代法实现二叉树的前后中序遍历。 递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中 ，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。 此时大家应该知道我们用栈

    2024年02月10日
    浏览(47)
  • 【代码随想录day21】二叉树的最近公共祖先

    【代码随想录day21】二叉树的最近公共祖先

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

    2024年02月15日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包