• 高阶数据结构：二叉搜索树

    本篇主要是在初级数据结构中介绍的二叉树的提升，了解二叉搜索树的特性。

    文章目录

    • 一、二叉搜索树的概念
    • 二、二叉搜索树操作
      • 1、二叉搜索树的查找
      • 2、二叉搜索树的插入
      • 3、二叉搜索树的删除
    • 三、二叉搜索树的实现
    • 四、二叉搜索树的应用
    • 五、关于二叉树进阶面试题

    一、二叉搜索树概念

    概念：二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下特征：

    一、它的左子树不为空，则左子树上所有的节点的值都小于根节点的值

    二、它的右子树不为空，则右子树上所有的节点的值都大于根节点的值

    三、它的左右子树也分别为二叉搜索树

    如果所示：

    二、二叉搜索树的操作

    1.二叉搜索树的查找

    1. bool Find(const K& key)
    2. 	{
    3. 		Node* cur = _root;
    4. 		while (cur)
    5. 		{
    6. 			if (cur->_key < key)
    7. 				cur = cur->_right;
    8. 			else if(cur->_key>key)
    9. 				cur = cur->_left;
    10. 			else
    11. 			    return true;
    12. 		}
    13. 		return false;
    14. 	}

    2.二叉树的插入

    1. 	bool Insert(const K& key)
    2. 	{
    3. 		//如果此时根结点不存在需要创建根结点
    4. 		if (_root == nullptr)
    5. 		{
    6. 			_root = new Node(key);
    7. 			return true;
    8. 		}
    9.  
    10. 		//插入新结点的时候需要将父类的节点进行连接
    11. 		Node* parent = nullptr;
    12. 		Node* cur = _root;
    13. 		while (cur)
    14. 		{
    15. 			if (cur->_key < key)
    16. 			{
    17. 				parent = cur;
    18. 				cur = cur->_right;
    19. 			}
    20. 			else if (cur->_key > key)
    21. 			{
    22. 				parent = cur;
    23. 				cur = cur->_left;
    24. 			}
    25. 			else
    26. 			{
    27. 				return false;
    28. 			}
    29. 		}
    30. 		
    31. 		cur = new Node(key);
    32. 		if (parent->key < key)
    33. 			parent->_right = cur;
    34. 		else
    35. 			parent->_left = cur;
    36. 		return true;
    37. 	}

     3.二叉树的删除

    1. bool Erase(const K& key)
    2. 	{
    3. 		Node* parent = nullptr;
    4. 		Node* cur = _root;
    5. 		while (cur)
    6. 		{
    7. 			if (cur->_key < key)
    8. 			{
    9. 				parent = cur;
    10. 				cur = cur->_right;
    11. 			}
    12. 			else if (cur->_key > key)
    13. 			{
    14. 				parent = cur;
    15. 				cur = cur->_left;
    16. 			}
    17. 			else
    18. 			{
    19. 				//开始删除
    20. 				//左为空
    21. 				//右为空
    22. 				//左右都不为空
    23. 				//这里需要考虑根节点的情况
    24. 				if (cur->left == nullptr)
    25. 				{
    26. 					if (cur->_left == nullptr)
    27. 					{
    28. 						if (cur == _root)
    29. 						{
    30. 							_root = cur->_right;
    31. 						}
    32. 						else
    33. 						{
    34. 							if (cur == parent->_left)
    35. 								parent->left = cur->_right;
    36. 							else
    37. 								parent->_right = cur->right;
    38. 						}
    39. 					}
    40. 					delete cur;
    41. 					cur = nullptr;
    42. 				}
    43. 				else if (cur->_right == nullptr)
    44. 				{
    45. 					if (_root == cur)
    46. 						_root = cur->_left;
    47. 					else
    48. 					{
    49. 						if (cur == parent->_left)
    50. 							parent->_left = cur->_left;
    51. 						else
    52. 							parent->_right = cur->_left;
    53. 					}
    54. 					delete cur;
    55. 					cur = nullptr;
    56. 				}
    57. 				else
    58. 				{
    59. 					//找到右子树最小节点进行替换
    60. 					Node* minParent = cur;
    61. 					Node* min = cur->_right;
    62. 					while (min->_left)
    63. 					{
    64. 						minParent = min;
    65. 						min = min->_left;
    66. 					}
    67. 					swap(cur->_key, min->_key);
    68. 					if (minParent->_left == min)
    69. 						minParent->_left = min->_right;
    70. 					else
    71. 						minParent->_right = min->_right;
    72. 					delete min;
    73. 				}
    74. 				return true;
    75. 			}
    76. 			return false;
    77. 		}
    78. 	}

     三、二叉搜索树的实现

    1. struct BSTreeNode
    2. {
    3. 	BSTreeNode* _left;
    4. 	BSTreeNode* _right;
    5. 	K _key;
    6.  
    7. 	BSTreeNode(const K& key)
    8. 		:_left(nullptr)
    9. 		, _right(nullptr)
    10. 		, _key(key)
    11. 	{}
    12. };
    13.  
    14. //class BinarySearchTree
    15. template<class K>
    16. class BSTree
    17. {
    18. 	typedef BSTreeNode Node;
    19. public:
    20. 	bool Insert(const K& key)
    21. 	{
    22. 		if (_root == nullptr)
    23. 		{
    24. 			_root = new Node(key);
    25. 			return true;
    26. 		}
    27.  
    28. 		Node* parent = nullptr;
    29. 		Node* cur = _root;
    30. 		while (cur)
    31. 		{
    32. 			if (cur->_key < key)
    33. 			{
    34. 				parent = cur;
    35. 				cur = cur->_right;
    36. 			}
    37. 			else if (cur->_key > key)
    38. 			{
    39. 				parent = cur;
    40. 				cur = cur->_left;
    41. 			}
    42. 			else
    43. 			{
    44. 				return false;
    45. 			}
    46. 		}
    47.  
    48. 		cur = new Node(key);
    49. 		if (parent->_key < key)
    50. 		{
    51. 			parent->_right = cur;
    52. 		}
    53. 		else
    54. 		{
    55. 			parent->_left = cur;
    56. 		}
    57.  
    58. 		return true;
    59. 	}
    60.  
    61. 	bool Find(const K& key)
    62. 	{
    63. 		Node* cur = _root;
    64. 		while (cur)
    65. 		{
    66. 			if (cur->_key < key)
    67. 			{
    68. 				cur = cur->_right;
    69. 			}
    70. 			else if (cur->_key > key)
    71. 			{
    72. 				cur = cur->_left;
    73. 			}
    74. 			else
    75. 			{
    76. 				return true;
    77. 			}
    78. 		}
    79.  
    80. 		return false;
    81. 	}
    82.  
    83. 	bool Erase(const K& key)
    84. 	{
    85. 		Node* parent = nullptr;
    86. 		Node* cur = _root;
    87. 		while (cur)
    88. 		{
    89. 			if (cur->_key < key)
    90. 			{
    91. 				parent = cur;
    92. 				cur = cur->_right;
    93. 			}
    94. 			else if (cur->_key > key)
    95. 			{
    96. 				parent = cur;
    97. 				cur = cur->_left;
    98. 			}
    99. 			else
    100. 			{
    101. 				// 开始删除
    102. 				// 1、左为空
    103. 				// 2、右为空
    104. 				// 3、左右都不为空
    105. 				if (cur->_left == nullptr)
    106. 				{
    107. 					if (cur == _root)
    108. 					{
    109. 						_root = cur->_right;
    110. 					}
    111. 					else
    112. 					{
    113. 						if (cur == parent->_left)
    114. 						{
    115. 							parent->_left = cur->_right;
    116. 						}
    117. 						else
    118. 						{
    119. 							parent->_right = cur->_right;
    120. 						}
    121. 					}
    122.  
    123. 					delete cur;
    124. 					cur = nullptr;
    125. 				}
    126. 				else if (cur->_right == nullptr)
    127. 				{
    128. 					if (_root == cur)
    129. 					{
    130. 						_root = cur->_left;
    131. 					}
    132. 					else
    133. 					{
    134. 						if (cur == parent->_left)
    135. 						{
    136. 							parent->_left = cur->_left;
    137. 						}
    138. 						else
    139. 						{
    140. 							parent->_right = cur->_left;
    141. 						}
    142. 					}
    143.  
    144. 					delete cur;
    145. 					cur = nullptr;
    146. 				}
    147. 				else
    148. 				{
    149. 					// 找到右子树最小节点进行替换
    150. 					Node* minParent = cur;
    151. 					Node* min = cur->_right;
    152. 					while (min->_left)
    153. 					{
    154. 						minParent = min;
    155. 						min = min->_left;
    156. 					}
    157.  
    158. 					swap(cur->_key, min->_key);
    159. 					if (minParent->_left == min)
    160. 						minParent->_left = min->_right;
    161. 					else
    162. 						minParent->_right = min->_right;
    163.  
    164. 					delete min;
    165. 				}
    166.  
    167. 				return true;
    168. 			}
    169. 		}
    170.  
    171. 		return false;
    172. 	}
    173.  
    174. 	void InOrder()
    175. 	{
    176. 		_InOrder(_root);
    177. 		cout << endl;
    178. 	}
    179.  
    180. 	/
    181. 	bool FindR(const K& key)
    182. 	{
    183. 		return _FindR(_root, key);
    184. 	}
    185.  
    186. 	bool InsertR(const K& key)
    187. 	{
    188. 		return _InsertR(_root, key);
    189. 	}
    190.  
    191. 	bool EraseR(const K& key)
    192. 	{
    193. 		return _EraseR(_root, key);
    194. 	}
    195.  
    196. 	~BSTree()
    197. 	{
    198. 		_Destory(_root);
    199. 	}
    200.  
    201. 	/*BSTree()
    202. 	{}*/
    203.  
    204. 	// C++的用法：强制编译器生成默认的构造
    205. 	BSTree() = default;
    206.  
    207. 	BSTree(const BSTree& t)
    208. 	{
    209. 		_root = _Copy(t._root);
    210. 	}
    211.  
    212. 	// t2 = t1
    213. 	BSTree& operator=(BSTree t)
    214. 	{
    215. 		swap(_root, t._root);
    216. 		return *this;
    217. 	}
    218.  
    219. private:
    220. 	Node* _Copy(Node* root)
    221. 	{
    222. 		if (root == nullptr)
    223. 		{
    224. 			return nullptr;
    225. 		}
    226.  
    227. 		Node* copyRoot = new Node(root->_key);
    228. 		copyRoot->_left = _Copy(root->_left);
    229. 		copyRoot->_right = _Copy(root->_right);
    230. 		return copyRoot;
    231. 	}
    232.  
    233. 	void _Destory(Node*& root)
    234. 	{
    235. 		if (root == nullptr)
    236. 		{
    237. 			return;
    238. 		}
    239.  
    240. 		_Destory(root->_left);
    241. 		_Destory(root->_right);
    242. 		delete root;
    243. 		root = nullptr;
    244. 	}
    245.  
    246.  
    247. 	bool _EraseR(Node*& root, const K& key)
    248. 	{
    249. 		if (root == nullptr)
    250. 			return false;
    251.  
    252. 		if (root->_key < key)
    253. 			return _EraseR(root->_right, key);
    254. 		else if (root->_key > key)
    255. 			return _EraseR(root->_left, key);
    256. 		else
    257. 		{
    258. 			Node* del = root;
    259. 			if (root->_left == nullptr)
    260. 			{
    261. 				root = root->_right;
    262. 			}
    263. 			else if (root->_right == nullptr)
    264. 			{
    265. 				root = root->_left;
    266. 			}
    267. 			else
    268. 			{
    269. 				// 找右树的最左节点替换删除
    270. 				Node* min = root->_right;
    271. 				while (min->_left)
    272. 				{
    273. 					min = min->_left;
    274. 				}
    275. 				swap(root->_key, min->_key);
    276. 				//return EraseR(key);  错的
    277. 				return _EraseR(root->_right, key);
    278. 			}
    279.  
    280. 			delete del;
    281. 			return true;
    282. 		}
    283. 	}
    284.  
    285. 	bool _InsertR(Node*& root, const K& key)
    286. 	{
    287. 		if (root == nullptr)
    288. 		{
    289. 			root = new Node(key);
    290. 			return true;
    291. 		}
    292.  
    293. 		if (root->_key < key)
    294. 			return _InsertR(root->_right, key);
    295. 		else if (root->_key > key)
    296. 			return _InsertR(root->_left, key);
    297. 		else
    298. 			return false;
    299. 	}
    300.  
    301. 	bool _FindR(Node* root, const K& key)
    302. 	{
    303. 		if (root == nullptr)
    304. 			return false;
    305.  
    306. 		if (root->_key < key)
    307. 			return _FindR(root->_right, key);
    308. 		else if (root->_key > key)
    309. 			return _FindR(root->_left, key);
    310. 		else
    311. 			return true;
    312. 	}
    313.  
    314. 	void _InOrder(Node* root)
    315. 	{
    316. 		if (root == nullptr)
    317. 		{
    318. 			return;
    319. 		}
    320.  
    321. 		_InOrder(root->_left);
    322. 		cout << root->_key << " ";
    323. 		_InOrder(root->_right);
    324. 	}
    325. private:
    326. 	Node* _root = nullptr;
    327. };

    四、二叉搜索树的应用

    1.K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到

    的值。

    2.KV模型：每一个关键码key，都有与之对应的值Value，即的键值对。

     五、关于二叉树进阶面试题

    1.根据二叉树创建字符串OJ链接

    1. /**
    2.  * Definition for a binary tree node.
    3.  * struct TreeNode {
    4.  *     int val;
    5.  *     TreeNode *left;
    6.  *     TreeNode *right;
    7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    10.  * };
    11.  */
    12. class Solution {
    13. public:
    14.     string tree2str(TreeNode* root) {
    15.           if(root==nullptr)
    16.             return string();
    17.         string str;
    18.         str+=to_string(root->val);
    19.         //如果左子树不为空或者左右子树都不为空，左边需要加括号
    20.         if(root->left||root->right)
    21.         {
    22.             str+='(';
    23.             str+=tree2str(root->left);
    24.             str+=')';
    25.         }
    26.         //右边如果不为空，右边需要加括号
    27.         if(root->right)
    28.         {
    29.             str+='(';
    30.             str+=tree2str(root->right);
    31.             str+=')';
    32.         }
    33.         return str;
    34.     }
    35. };

     2.二叉树的层序遍历OJ链接

     

    1. /**
    2.  * Definition for a binary tree node.
    3.  * struct TreeNode {
    4.  *     int val;
    5.  *     TreeNode *left;
    6.  *     TreeNode *right;
    7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    10.  * };
    11.  */
    12. class Solution {
    13. public:
    14.     vectorint>> levelOrder(TreeNode* root) {
    15.         //如果此时二叉树为空，则返回vector>的匿名对象
    16.         if(root==nullptr)
    17.             return vectorint>>();
    18.         //利用队列先进先出的特性进行判断
    19.         queue q;
    20.         //利用二维数组来保存当前没一层的节点
    21.         vectorint>> vv;
    22.         int levelSize=1;//每一行的节点数
    23.  
    24.         q.push(root);//将此时的根节点如队
    25.         while(!q.empty())//如果队列不为空就继续
    26.         {
    27.            vector<int> v;
    28.            for(int i=0;i
    29.            {
    30.                TreeNode*front=q.front();//将队列的第一个数据保存然后出队
    31.                q.pop();
    32.                v.push_back(front->val);
    33.  
    34.                if(front->left)
    35.                 q.push(front->left);
    36.                if(front->right)
    37.                 q.push(front->right);
    38.            }
    39.            levelSize=q.size();//将此时队列中的个数求出来
    40.            vv.push_back(v);
    41.         }
    42.         return vv;
    43.     }
    44. };

    3.二叉树的层序遍历IIOJ链接

     

    1. /**
    2.  * Definition for a binary tree node.
    3.  * struct TreeNode {
    4.  *     int val;
    5.  *     TreeNode *left;
    6.  *     TreeNode *right;
    7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    10.  * };
    11.  */
    12. class Solution {
    13. public:
    14.     vectorint>> levelOrderBottom(TreeNode* root) {
    15.        //如果此时二叉树为空，则返回vector>的匿名对象
    16.         if(root==nullptr)
    17.             return vectorint>>();
    18.         //利用队列先进先出的特性进行判断
    19.         queue q;
    20.         //利用二维数组来保存当前没一层的节点
    21.         vectorint>> vv;
    22.         int levelSize=1;//每一行的节点数
    23.  
    24.         q.push(root);//将此时的根节点如队
    25.         while(!q.empty())//如果队列不为空就继续
    26.         {
    27.            vector<int> v;
    28.            for(int i=0;i
    29.            {
    30.                TreeNode*front=q.front();//将队列的第一个数据保存然后出队
    31.                q.pop();
    32.                v.push_back(front->val);
    33.  
    34.                if(front->left)
    35.                 q.push(front->left);
    36.                if(front->right)
    37.                 q.push(front->right);
    38.            }
    39.            levelSize=q.size();//将此时队列中的个数求出来
    40.            vv.push_back(v);
    41.         }
    42.         reverse(vv.begin(),vv.end());
    43.         return vv;
    44.     }
    45. };

    4.二叉树的最近公共祖先 OJ链接

     

    1. /**
    2.  * Definition for a binary tree node.
    3.  * struct TreeNode {
    4.  *     int val;
    5.  *     TreeNode *left;
    6.  *     TreeNode *right;
    7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    8.  * };
    9.  */
    10. class Solution {
    11. public:
    12.     bool Find(TreeNode*root,TreeNode*x,stack&path)
    13.     {
    14.         if(root==nullptr) return false;
    15.         path.push(root);
    16.         if(root==x) return true;
    17.        
    18.  
    19.         //如果没有找到从左子树开始找，如果没找到去右子树中找，如果都没有找到此时需要将所有的当前节点需要进行出栈的操作
    20.         if(Find(root->left,x,path)) return true;
    21.         if(Find(root->right,x,path)) return true;
    22.         
    23.         path.pop();
    24.         return false;
    25.  
    26.     }
    27.     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    28.         if(root==nullptr)  return nullptr;
    29.         
    30.         //利用DFS来保存每一次搜索的路径
    31.         stack pPath,qPath;
    32.  
    33.         Find(root,p,pPath);
    34.         Find(root,q,qPath);
    35.  
    36.         //根据求两个链表公共节点的策略来求出二叉树中两个节点的最近的公共祖先的问题
    37.         while(pPath.size()!=qPath.size())
    38.         {
    39.             if(pPath.size()>qPath.size()) pPath.pop();
    40.             else qPath.pop();
    41.         }
    42.  
    43.         while(pPath.top()!=qPath.top())
    44.         {
    45.             pPath.pop();
    46.             qPath.pop();
    47.         }
    48.         return pPath.top();
    49.     }
    50. };

    5.二叉搜索树与双向链表 OJ链接

     

    1. /*
    2. struct TreeNode {
    3. 	int val;
    4. 	struct TreeNode *left;
    5. 	struct TreeNode *right;
    6. 	TreeNode(int x) :
    7. 			val(x), left(NULL), right(NULL) {
    8. 	}
    9. };*/
    10. class Solution {
    11. public:
    12. 	void InOrderConvert(TreeNode*cur,TreeNode*&prev)
    13. 	{
    14. 		if(cur==nullptr) return;
    15. 		//先找出左子树
    16. 		InOrderConvert(cur->left,prev);
    17. 		cur->left=prev;
    18. 		if(prev)
    19. 			prev->right=cur;
    20. 		prev=cur;
    21. 		InOrderConvert(cur->right,prev);
    22. 	}
    23.     TreeNode* Convert(TreeNode* pRootOfTree) {
    24. 		TreeNode*prev=nullptr;
    25. 		InOrderConvert(pRootOfTree,prev);
    26.  
    27. 		while(pRootOfTree&&pRootOfTree->left)
    28. 			pRootOfTree=pRootOfTree->left;
    29. 		return pRootOfTree;
    30.     }
    31. };

     6.从前序与中序遍历序列构造二叉树OJ链接

    1. /**
    2.  * Definition for a binary tree node.
    3.  * struct TreeNode {
    4.  *     int val;
    5.  *     TreeNode *left;
    6.  *     TreeNode *right;
    7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    10.  * };
    11.  */
    12. class Solution {
    13. public:
    14.     //利用前序来创建树，中序来分割区间
    15.     TreeNode*buildTreeHelper(vector<int>&preorder,vector<int>&inorder,int& prei,int inbegin,int inend)//这里previ需要利用引用，因为下一次递归prei会发生改变
    16.     {
    17.         if(inbegin>inend) return nullptr;
    18.         TreeNode*root=new TreeNode(preorder[prei++]);
    19.         
    20.         //将中序的区间进行划分
    21.         int ini=inbegin;
    22.         while(ini<=inend)
    23.         {
    24.             if(inorder[ini]==root->val) break;
    25.             else ++ini;
    26.         }
    27.         //利用分治法的思想继续分割左右区间
    28.         root->left=buildTreeHelper(preorder,inorder,prei,inbegin,ini-1);
    29.         root->right=buildTreeHelper(preorder,inorder,prei,ini+1,inend);
    30.         return root;
    31.     }
    32.     TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    33.         int i=0;
    34.         return buildTreeHelper(preorder,inorder,i,0,inorder.size()-1);
    35.     }
    36. };

     

    7.二叉树的前序遍历OJ链接

     

     

    1. /**
    2.  * Definition for a binary tree node.
    3.  * struct TreeNode {
    4.  *     int val;
    5.  *     TreeNode *left;
    6.  *     TreeNode *right;
    7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    10.  * };
    11.  */
    12. class Solution {
    13. public:
    14.     vector<int> preorderTraversal(TreeNode* root) {
    15.         if(root==nullptr)
    16.             return vector<int>();
    17.         vector<int> v;
    18.         stack st;
    19.         TreeNode*cur=root;
    20.  
    21.         while(cur||!st.empty())
    22.         {
    23.         //左路节点入栈
    24.         while(cur)
    25.         {
    26.             v.push_back(cur->val);
    27.             st.push(cur);
    28.  
    29.             cur=cur->left;
    30.         }
    31.  
    32.         //右路节点的右子树
    33.         TreeNode*top=st.top();
    34.         st.pop();
    35.         cur=top->right;
    36.         }
    37.     return v;
    38.     }
    39.   
    40. };

    8.二叉树的中序遍历OJ链接

     

    1. /**
    2.  * Definition for a binary tree node.
    3.  * struct TreeNode {
    4.  *     int val;
    5.  *     TreeNode *left;
    6.  *     TreeNode *right;
    7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    10.  * };
    11.  */
    12. class Solution {
    13. public:
    14.     vector<int> inorderTraversal(TreeNode* root) {
    15.         if(root==nullptr)  return vector<int>();
    16.  
    17.         TreeNode*cur=root;
    18.         stack st;
    19.         vector<int> v;
    20.  
    21.         while(cur||!st.empty())
    22.         {
    23.             while(cur)
    24.             {
    25.                 st.push(cur);
    26.                 cur=cur->left;
    27.             }
    28.  
    29.             TreeNode*top=st.top();
    30.             v.push_back(top->val);
    31.             st.pop();
    32.  
    33.             cur=top->right;
    34.             
    35.         }
    36.         return v;
    37.     }
    38. };

    9.二叉树的后序遍历OJ链接

     

    1. /**
    2.  * Definition for a binary tree node.
    3.  * struct TreeNode {
    4.  *     int val;
    5.  *     TreeNode *left;
    6.  *     TreeNode *right;
    7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    10.  * };
    11.  */
    12. class Solution {
    13. public:
    14.     vector<int> postorderTraversal(TreeNode* root) {
    15.         if(root==nullptr)  return vector<int>();
    16.  
    17.         TreeNode*cur=root;
    18.         TreeNode*prev=nullptr;
    19.         vector<int> v;
    20.         stack st;
    21.  
    22.         //一个节点不为空的情况下：
    23.         //右子树没有访问，访问右子树
    24.         //右子树已经访问过了，访问根节点
    25.         while(cur||!st.empty())
    26.         {
    27.             //左路节点入栈
    28.             while(cur)
    29.             {
    30.                 st.push(cur);
    31.                 cur=cur->left;
    32.             }
    33.             TreeNode*top=st.top();
    34.  
    35.             //右路节点
    36.             //如果右为空或者没有访问过
    37.             if(top->right==nullptr||top->right==prev) 
    38.             {
    39.                 v.push_back(top->val);
    40.                 prev=top;
    41.                 st.pop();
    42.             } 
    43.             else
    44.             {
    45.                 cur=top->right;
    46.             }
    47.         }
    48.         return v;
    49.     }
    50. };

  • 相关阅读:
    用于语义线检测的深度霍夫变换
    java计算机毕业设计考勤管理系统源码+mysql数据库+系统+lw文档+部署
    Zabbix 5.0部署（centos7+server+MySQL+Apache）
    【开源】JAVA+Vue.js实现大学计算机课程管理平台
    熹微~~~基于Vue开发的昏暗风格的响应式网页！
    【人体骨骼点】算法综述
    第二部分—C语言提高篇_11. 预处理
    【SQL屠夫系列】- 高频面试之SQL计算用户留存率
    数据库innodb使用redo log数据恢复原理
    FFmpeg命令行工具-实用命令
  • 原文地址：https://blog.csdn.net/qq_67458830/article/details/126860284