二叉搜索树（二叉排序树）（含力扣相关题及题解）

2024-03-21 20:52
文章标签 搜索 排序 二叉 相关 题解 题及 含力

本文主要是介绍二叉搜索树（二叉排序树）（含力扣相关题及题解），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

  • 二叉搜索树（二叉排序树）
    • 1、二叉搜索树概念
    • 2、二叉搜索树的操作
      • 2.1、二叉搜索树的查找
      • 2.2、二叉搜索树的插入
      • 2.2、二叉树的删除
    • 3、二叉搜索树的实现（含递归版本）
    • 4、二叉搜索树的应用
      • 4.1、K模型
      • 4.2、KV模型
    • 5、二叉搜索树的性能分析
    • 6、二叉树进阶面试题

img

二叉搜索树（二叉排序树）

1、二叉搜索树概念

**二叉搜索树又叫二叉排序树和二叉查找树。**二叉搜索树可以为空。若当前二叉搜索树不为空，它有以下性质：

  1. 若左子树不为空，则根结点的的值大于左子树中所有结点的值

  2. 若右子树不为空，则根结点的的值小于左子树中所有结点的值

  3. 左右子树也有以上性质

2、二叉搜索树的操作

插入序列：

int arr[] = {8,3,1,10,6,4,7,14,13};

2.1、二叉搜索树的查找

  1. 从根开始比较，比根小的去根的左子树中查找，比根大的去根的右子树中查找
  2. 一直查找直到找到，没找到的话则走到了空。

template<class K>
struct BSTreeNode {//typedef BSTreeNode<K> Node;BSTreeNode<K> *_left;BSTreeNode<K> *_right;K _key;BSTreeNode(const K &key) : _left(nullptr), _right(nullptr), _key(key) {}};template<class K>
class BinarySearchTree {
public:typedef BSTreeNode<K> Node;bool Find(const K &key) {Node *cur = _root;if (cur == nullptr)return false;while (cur) {if (cur->_key < key) {cur = cur->_right;} else if (cur->_key > key) {cur = cur->_left;} else {return true;}}return false;}
private:Node *_root = nullptr;
};

2.2、二叉搜索树的插入

  1. 若树为空则直接插入
  2. 若树不为空，按查找的性质去找查找位置

template<class K>
struct BSTreeNode {//typedef BSTreeNode<K> Node;BSTreeNode<K> *_left;BSTreeNode<K> *_right;K _key;BSTreeNode(const K &key) : _left(nullptr), _right(nullptr), _key(key) {}};template<class K>
class BinarySearchTree {
public:typedef BSTreeNode<K> Node;bool Insert(const K &key) {Node *cur = _root;Node *parent = nullptr;if (cur == nullptr) {Node *newNode = new Node(key);_root = newNode;return true;}while (cur) {if (cur->_key < key) {parent = cur;cur = cur->_right;} else if (cur->_key > key) {parent = cur;cur = cur->_left;} else {return false;}}// cur == nullptrNode *newNode = new Node(key);if (parent->_key < key)parent->_right = newNode;else if (parent->_key > key)parent->_left = newNode;return true;}
private:Node *_root = nullptr;
};

2.2、二叉树的删除

首先查找要查找的值是否在该树中，如果不存在，则返回。否则要删除的结点分下面四种情况：

  1. 要删除的结点无孩子
  2. 要删除的结点无左孩子，只有右孩子
  3. 要删除的结点无右孩子，只有左孩子
  4. 要删除的结点有左右孩子

上面1，2，3其实可以结合起来，即将要删除的结点无孩子直接归类为无左孩子（2）或者无右孩子（3）。如下：

  1. 若要删除的结点是其双亲结点的左孩子，则让其双亲的左指针指向要删除的结点的右孩子，若要删除的结点是其双亲结点的右孩子，则让其双亲的右指针指向要删除的结点的右孩子。
  2. 若要删除的结点是其双亲结点的左孩子，则让其双亲的左指针指向要删除的结点的左孩子，若要删除的结点是其双亲结点的右孩子，则让其双亲的右指针指向要删除的结点的左孩子。
  3. 找当前要删除结点的左子树中的最大值（或者右子树最小值）来替换当前结点（非递归直接赋值，递归直接交换值，仅交换值，不是交换结点）

template<class K>
struct BSTreeNode {//typedef BSTreeNode<K> Node;BSTreeNode<K> *_left;BSTreeNode<K> *_right;K _key;BSTreeNode(const K &key) : _left(nullptr), _right(nullptr), _key(key) {}};template<class K>
class BinarySearchTree {
public:typedef BSTreeNode<K> Node;bool Erase(const K &key) {Node *cur = _root;Node *parent = nullptr;if (cur == nullptr)return false;while (cur) {if (cur->_key < key) {parent = cur;cur = cur->_right;} else if (cur->_key > key) {parent = cur;cur = cur->_left;} else {//找到要删的结点// 当前要删的结点有一个孩子或者没有孩子if (cur->_left == nullptr) {// 判断跟结点是否只有一颗子树if (cur == _root) {_root = _root->_right;} else {if (parent->_left == cur)parent->_left = cur->_right;elseparent->_right = cur->_right;}delete cur;return true;} else if (cur->_right == nullptr) {// 判断跟结点是否只有一颗子树if (cur == _root) {_root = _root->_left;} else {if (parent->_left == cur)parent->_left = cur->_left;elseparent->_right = cur->_left;}delete cur;return true;} else {// 当前要删的结点有两个孩子// 找个替代的值去删  -- 找左子树的最右结点,即左子树最大的结点Node *LeftMax = cur->_left;Node *LeftMaxParent = cur;while (LeftMax->_right) {LeftMaxParent = LeftMax;LeftMax = LeftMax->_right;}cur->_key = LeftMax->_key;if (LeftMaxParent->_left == LeftMax)LeftMaxParent->_left = LeftMax->_left;elseLeftMaxParent->_right = LeftMax->_left;delete LeftMax;return true;}}}return false;}
private:Node *_root = nullptr;
};

3、二叉搜索树的实现（含递归版本）

template<class K>
struct BSTreeNode {//typedef BSTreeNode<K> Node;BSTreeNode<K> *_left;BSTreeNode<K> *_right;K _key;BSTreeNode(const K &key) : _left(nullptr), _right(nullptr), _key(key) {}};template<class K>
class BinarySearchTree {
public:typedef BSTreeNode<K> Node;BinarySearchTree() = default;BinarySearchTree(const BinarySearchTree<K> &b) {_root = Copy(b._root);}Node *Copy(Node *root) {if (root == nullptr)return nullptr;Node *newNode = new Node(root->_key);newNode->_left = Copy(root->_left);newNode->_right = Copy(root->_right);return newNode;}BinarySearchTree<K> &operator=(BinarySearchTree<K> b) {swap(b._root, _root);return *this;}~BinarySearchTree() {Destroy(_root);}void Destroy(Node *root) {if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}bool Erase(const K &key) {Node *cur = _root;Node *parent = nullptr;if (cur == nullptr)return false;while (cur) {if (cur->_key < key) {parent = cur;cur = cur->_right;} else if (cur->_key > key) {parent = cur;cur = cur->_left;} else {//找到要删的结点// 当前要删的结点有一个孩子或者没有孩子if (cur->_left == nullptr) {// 判断跟结点是否只有一颗子树if (cur == _root) {_root = _root->_right;} else {if (parent->_left == cur)parent->_left = cur->_right;elseparent->_right = cur->_right;}delete cur;return true;} else if (cur->_right == nullptr) {// 判断跟结点是否只有一颗子树if (cur == _root) {_root = _root->_left;} else {if (parent->_left == cur)parent->_left = cur->_left;elseparent->_right = cur->_left;}delete cur;return true;} else {// 当前要删的结点有两个孩子// 找个替代的值去删  -- 找左子树的最右结点,即左子树最大的结点Node *LeftMax = cur->_left;Node *LeftMaxParent = cur;while (LeftMax->_right) {LeftMaxParent = LeftMax;LeftMax = LeftMax->_right;}cur->_key = LeftMax->_key;if (LeftMaxParent->_left == LeftMax)LeftMaxParent->_left = LeftMax->_left;elseLeftMaxParent->_right = LeftMax->_left;delete LeftMax;return true;}}}return false;}bool Insert(const K &key) {Node *cur = _root;Node *parent = nullptr;if (cur == nullptr) {Node *newNode = new Node(key);_root = newNode;return true;}while (cur) {if (cur->_key < key) {parent = cur;cur = cur->_right;} else if (cur->_key > key) {parent = cur;cur = cur->_left;} else {return false;}}// cur == nullptrNode *newNode = new Node(key);if (parent->_key < key)parent->_right = newNode;else if (parent->_key > key)parent->_left = newNode;return true;}bool Find(const K &key) {Node *cur = _root;if (cur == nullptr)return false;while (cur) {if (cur->_key < key) {cur = cur->_right;} else if (cur->_key > key) {cur = cur->_left;} else {return true;}}return false;}void InOrder() {_InOrder(_root);cout << endl;}bool FindR(const K &key) {return _FindR(_root, key);}bool InsertR(const K &key) {return _InsertR(_root, key);}bool EraseR(const K &key) {return _EraseR(_root, key);}private:bool _EraseR(Node *root, const K &key) {if (root == nullptr)return false;if (root->_key < key) {return _EraseR(root->_right, key);} else if (root->_key > key) {return _EraseR(root->_left, key);} else {Node *del = root;if (root->_right == nullptr)root = root->_left;else if (root->_left == nullptr)root = root->_right;else {// 将当前要删的结点的值和当前结点的左子树最大值的结点交换Node *LeftMax = root->_left;while (LeftMax->_right) {LeftMax = LeftMax->_right;}swap(LeftMax->_key, root->_key);return _EraseR(root, key);}delete del;return true;}}bool _InsertR(Node *&root, const K &key) {if (root == nullptr) {root = new Node(key);return true;}if (root->_key < key) {return _InsertR(root->_right, key);} else if (root->_key > key) {return _InsertR(root->_left, key);} else {return false;}}bool _FindR(Node *root, const K &key) {if (root == nullptr)return false;if (root->_key < key) {return _FindR(root->_right, key);} else if (root->_key > key) {return _FindR(root->_left, key);} else {return true;}}void _InOrder(Node *root) {if (root == nullptr)return;if (root->_left)_InOrder(root->_left);cout << root->_key << " ";if (root->_right)_InOrder(root->_right);}Node *_root = nullptr;
};

4、二叉搜索树的应用

4.1、K模型

K模型即只有key作为关键码，结构中只需要存储key即可，关键码即为需要搜索到的值。

比如：上述实现的就是，比如存的就是整型值，看该树中是否有要查找的值。或者给一个单词word，判断该单词是否拼写正确。

4.2、KV模型

KV模型即每一个关键码key，都有与之对应的值value，即<key, value>的键值对。

比如：英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word,chinese>就构成一种键值对。

  • 对K模型的二叉搜索树进行小改造就可以得到KV模型的二叉搜索树
template<class K, class V>struct BSTreeNode {//typedef BSTreeNode<K> Node;BSTreeNode<K, V> *_left;BSTreeNode<K, V> *_right;K _key;V _val;BSTreeNode(const K &key,const K &val) : _left(nullptr), _right(nullptr), _key(key),_val(val) {}};template<class K, class V>class BinarySearchTree {public:typedef BSTreeNode<K, V> Node;BinarySearchTree() = default;BinarySearchTree(const BinarySearchTree<K, V> &b) {_root = Copy(b._root);}Node *Copy(Node *root) {if (root == nullptr)return nullptr;Node *newNode = new Node(root->_key);newNode->_left = Copy(root->_left);newNode->_right = Copy(root->_right);return newNode;}BinarySearchTree<K, V> &operator=(BinarySearchTree<K, V> b) {swap(b._root, _root);return *this;}~BinarySearchTree() {Destroy(_root);}void Destroy(Node *root) {if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}bool Erase(const K &key) {Node *cur = _root;Node *parent = nullptr;if (cur == nullptr)return false;while (cur) {if (cur->_key < key) {parent = cur;cur = cur->_right;} else if (cur->_key > key) {parent = cur;cur = cur->_left;} else {//找到要删的结点// 当前要删的结点有一个孩子或者没有孩子if (cur->_left == nullptr) {// 判断跟结点是否只有一颗子树if (cur == _root) {_root = _root->_right;} else {if (parent->_left == cur)parent->_left = cur->_right;elseparent->_right = cur->_right;}delete cur;return true;} else if (cur->_right == nullptr) {// 判断跟结点是否只有一颗子树if (cur == _root) {_root = _root->_left;} else {if (parent->_left == cur)parent->_left = cur->_left;elseparent->_right = cur->_left;}delete cur;return true;} else {// 当前要删的结点有两个孩子// 找个替代的值去删  -- 找左子树的最右结点,即左子树最大的结点Node *LeftMax = cur->_left;Node *LeftMaxParent = cur;while (LeftMax->_right) {LeftMaxParent = LeftMax;LeftMax = LeftMax->_right;}cur->_key = LeftMax->_key;if (LeftMaxParent->_left == LeftMax)LeftMaxParent->_left = LeftMax->_left;elseLeftMaxParent->_right = LeftMax->_left;delete LeftMax;return true;}}}return false;}bool Insert(const K &key,const K &val) {Node *cur = _root;Node *parent = nullptr;if (cur == nullptr) {Node *newNode = new Node(key,val);_root = newNode;return true;}while (cur) {if (cur->_key < key) {parent = cur;cur = cur->_right;} else if (cur->_key > key) {parent = cur;cur = cur->_left;} else {return false;}}// cur == nullptrNode *newNode = new Node(key,val);if (parent->_key < key)parent->_right = newNode;else if (parent->_key > key)parent->_left = newNode;return true;}Node *Find(const K &key) {Node *cur = _root;if (cur == nullptr)return nullptr;while (cur) {if (cur->_key < key) {cur = cur->_right;} else if (cur->_key > key) {cur = cur->_left;} else {return cur;}}return nullptr;}void InOrder() {_InOrder(_root);cout << endl;}private:void _InOrder(Node *root) {if (root == nullptr)return;if (root->_left)_InOrder(root->_left);cout << root->_key << " ";if (root->_right)_InOrder(root->_right);}Node *_root = nullptr;};void test_BST_KV() {BinarySearchTree<string, string> bstkv;bstkv.Insert("hello", "你好");bstkv.Insert("xp", "徐鹏");bstkv.Insert("zl", "紫玲");bstkv.Insert("search", "搜索");string s;while (cin >> s) {auto ret = bstkv.Find(s);if (ret)cout << ret->_val << endl;elsecout << "没有这个" << endl;}
}

5、二叉搜索树的性能分析

由于二叉搜索树的插入和删除都用到了查找，所以查找效率代表了二叉搜索树的各操作的性能。

对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，深度越深，查找中比较的次数越多。

但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树。

时间复杂度：

  1. 在最优的情况下，二叉搜索树接近为完全二叉树，其平均比较次数为：nlogn
  2. 在最坏的情况下，二叉搜索树接近为单边二叉树，其平均比较次数为：n^2

如果退化为单边树，那么二叉搜索树的优势就失去了，怎么解决？后面学了AVL（平衡二叉树）和红黑树就可以解决这个问题。

6、二叉树进阶面试题

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

/*** 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) {}* };*/// 606. 根据二叉树创建字符串class Solution {
public:string tree2str(TreeNode *root) {if (root == nullptr)return "";string str = to_string(root->val);// 要加括号：1、当前结点的左不空,左为空右不空也要加//         2、当前结点的右不空// 往左子树找if (root->left || root->right) {str += '(';str += tree2str(root->left);str += ')';}// 往右子树找if (root->right) {str += '(';str += tree2str(root->right);str += ')';}return str;}
};

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

/*** 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) {}* };*/// 102. 二叉树的层序遍历
class Solution {
public:vector <vector<int>> levelOrder(TreeNode *root) {vector <vector<int>> vv;if (root == nullptr)return vv;queue < TreeNode * > q;q.push(root);while (!q.empty()) {vector<int> v; // 用来每次尾插vvint size = q.size();// 当前层的元素个数for (int i = 0; i < size; ++i) {TreeNode *cur = q.front();v.push_back(cur->val);q.pop();if (cur->left)q.push(cur->left);if (cur->right)q.push(cur->right);}vv.push_back(v);}return vv;}
};

3、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) {}* };*/// 107. 二叉树的层序遍历 II
class Solution {
public:vector <vector<int>> levelOrderBottom(TreeNode *root) {vector <vector<int>> vv;if (root == nullptr)return vv;queue < TreeNode * > q;q.push(root);while (!q.empty()) {vector<int> v; // 用来每次尾插vvint size = q.size();// 当前层的元素个数for (int i = 0; i < size; ++i) {TreeNode *cur = q.front();v.push_back(cur->val);q.pop();if (cur->left)q.push(cur->left);if (cur->right)q.push(cur->right);}vv.push_back(v);}reverse(vv.begin(),vv.end());return vv;}
};

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

  • 解法一：
/*** 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:bool IsInTree(TreeNode *root, TreeNode *cur) {if (root == nullptr)return false;return root == cur || IsInTree(root->left, cur) || IsInTree(root->right, cur);}TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {if (root == nullptr)return nullptr;if (p == root || q == root)return root;bool pInLeft, pInRight, qInLeft, qInRight;pInLeft = IsInTree(root->left, p);pInRight = !pInLeft; // p肯定在左右子树中的一个qInLeft = IsInTree(root->left, q);qInRight = !qInLeft; // q肯定在左右子树中的一个if ((pInLeft && qInRight) || (pInRight && qInLeft)) {// 左右子树各一个，那么当前结点就是公共结点return root;} else if ((pInLeft && qInLeft)) {return lowestCommonAncestor(root->left, p, q);// 去左子树找} elsereturn lowestCommonAncestor(root->right, p, q);// 去右子树找}
};
  • 解法二：
/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*///  236. 二叉树的最近公共祖先
class Solution {
public:bool GetPath(TreeNode *root, TreeNode *cur, stack<TreeNode *> &v) {if (root == nullptr)return false;v.push(root);if (cur == root)return true;// 去左边找if (GetPath(root->left, cur, v))return true;// 去右边找if (GetPath(root->right, cur, v))return true;// 左右都没找到v.pop();return false;}TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {stack < TreeNode * > sp;stack < TreeNode * > sq;GetPath(root, p, sp);GetPath(root, q, sq);// 两个路径找交点while (sp.size() != sq.size()) {if (sp.size() > sq.size())sp.pop();elsesq.pop();}while (sp.top() != sq.top()) {sp.pop();sq.pop();}return sp.top();}
};

5、JZ36 二叉搜索树与双向链表

/*
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};*/// JZ36 二叉搜索树与双向链表
class Solution {
public:void InOrderConvert(TreeNode *cur, TreeNode *&pre) {if (cur == nullptr)return;InOrderConvert(cur->left, pre);// 关键cur->left = pre;if (pre)pre->right = cur;pre = cur;InOrderConvert(cur->right, pre);}TreeNode *Convert(TreeNode *pRootOfTree) {if (!pRootOfTree)return nullptr;TreeNode *pre = nullptr;InOrderConvert(pRootOfTree, pre);TreeNode *head = pRootOfTree;while (head->left) {head = head->left;}return head;}};

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

/*** 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) {}* };*/// 105. 从前序与中序遍历序列构造二叉树
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] != root->val)rooti++;elsebreak;}// 再构建左右子树// [inbegin,rooti-1]  [rooti+1,inend]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 prei = 0;return _buildTree(preorder, inorder, prei, 0, inorder.size() - 1);}
};

7、106. 从中序与后序遍历序列构造二叉树

/*** 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) {}* };*/// 106. 从中序与后序遍历序列构造二叉树
class Solution {
public:TreeNode *_buildTree(vector<int> &inorder, vector<int> &postorder, int &posti, int inbegin, int inend) {//   中序左右区间不对if (inbegin > inend)return nullptr;// 先创建结点 ，再构建它的左右子树TreeNode *root = new TreeNode(postorder[posti--]);// 中序序列划分左右区间 先构建右子树int rooti = inend;while (rooti >= inbegin) {if (inorder[rooti] != root->val)rooti--;elsebreak;}// 再构建右左子树// [inbegin,rooti-1]  [rooti+1,inend]root->right = _buildTree(inorder, postorder, posti, rooti + 1, inend);root->left = _buildTree(inorder, postorder, posti, inbegin, rooti - 1);return root;}TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {int posti = postorder.size() - 1;return _buildTree(inorder, postorder, posti, 0, inorder.size() - 1);}
};

8、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) {}* };*/// 144. 二叉树的前序遍历
class Solution {
public:vector<int> preorderTraversal(TreeNode *root) {stack < TreeNode * > s;vector<int> v;TreeNode *cur = root;while (cur || !s.empty()) {while (cur) {v.push_back(cur->val);s.push(cur);cur = cur->left;}// 左子树已经走完TreeNode *top = s.top();s.pop();// 现在走右子树cur = top->right;}return v;}
};

9、94. 二叉树的中序遍历

  • 用非递归方法：
/*** 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) {}* };*/// 94. 二叉树的中序遍历
class Solution {
public:vector<int> inorderTraversal(TreeNode *root) {stack < TreeNode * > s;vector<int> v;TreeNode *cur = root;while (cur || !s.empty()) {while (cur) {s.push(cur);cur = cur->left;}// 左子树已经走完TreeNode *top = s.top();s.pop();// 出栈的时候访问v.push_back(top->val);// 现在走右子树cur = top->right;}return v;}
};

10、145. 二叉树的后序遍历

  • 用非递归方法：
/*** 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) {}* };*/// 145. 二叉树的后序遍历
class Solution {
public:vector<int> postorderTraversal(TreeNode *root) {stack < TreeNode * > s;vector<int> v;TreeNode *cur = root;TreeNode *pre = nullptr;while (cur || !s.empty()) {while (cur) {s.push(cur);cur = cur->left;}// 左子树已经走完TreeNode *top = s.top();// 当前结点的右子树为空，可以访问当前结点// 或者右子树不空，但是已经访问过，也可以访问当前结点// 否则去右子树继续访问if (top->right == nullptr || top->right == pre) {v.push_back(top->val);s.pop();// top被pop掉了说明top就变成上一个被访问的结点pre = top;} else {// 现在走右子树cur = top->right;}}return v;}
};

OKOK，二叉排序树的讲解就到这里。如果你对Linux和C++也感兴趣的话，可以看看我的主页哦。下面是我的github主页，里面记录了我的学习代码和leetcode的一些题的题解，有兴趣的可以看看。

Xpccccc的github主页

这篇关于二叉搜索树（二叉排序树）（含力扣相关题及题解）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/833861。

相关文章

RecastNavigation之Poly相关类

RecastNavigation之Poly相关类

Poly分成正常的Poly 和 OffMeshPoly。 正常的Poly 又分成 原始的Poly 和 Detail化的Poly，本文介绍这两种。 Poly的边分成三种类型： 1. 正常边：有tile内部的poly与之相邻 2.border边：没有poly与之相邻 3.Portal边：与之相邻的是外部tile的poly   由firstLink索引 得到第一个连接的Poly  通
阅读更多...
LeetCode11. 盛最多水的容器题解

LeetCode11. 盛最多水的容器题解

LeetCode11. 盛最多水的容器题解 题目链接： https://leetcode.cn/problems/container-with-most-water 示例 思路 暴力解法 定住一个柱子不动，然后用其他柱子与其围住面积，取最大值。 代码如下： public int maxArea1(int[] height) {int n = height.length;int
阅读更多...
SQL Server中，always on服务器的相关操作

SQL Server中，always on服务器的相关操作

在SQL Server中，建立了always on服务，可用于数据库的同步备份，当数据库出现问题后，always on服务会自动切换主从服务器。 例如192.168.1.10为主服务器，12为从服务器，当主服务器出现问题后，always on自动将主服务器切换为12，保证数据库正常访问。 对于always on服务器有如下操作： 1、切换主从服务器：假如需要手动切换主从服务器时（如果两个服务
阅读更多...
数据结构9——排序

数据结构9——排序

一、冒泡排序 冒泡排序（Bubble Sort），顾名思义，就是指越小的元素会经由交换慢慢“浮”到数列的顶端。 算法原理 从左到右，依次比较相邻的元素大小，更大的元素交换到右边；从第一组相邻元素比较到最后一组相邻元素，这一步结束最后一个元素必然是参与比较的元素中最大的元素；按照大的居右原则，重新从左到后比较，前一轮中得到的最后一个元素不参4与比较，得出新一轮的最大元素；按照上述规则，每一轮结
阅读更多...
七种排序方式总结

七种排序方式总结

/*2018.01.23*A:YUAN*T:其中排序算法：冒泡排序，简单排序，直接插入排序，希尔排序，堆排序，归并排序，快速排序*/#include <stdio.h>#include <math.h>#include <malloc.h>#define MAXSIZE 10000#define FALSE 0#define TRUE 1typedef struct {i
阅读更多...
相关网站

相关网站

力扣  https://leetcode-cn.com/contest/weekly-contest-124
阅读更多...
【文末附gpt升级秘笈】腾讯元宝AI搜索解析能力升级：千万字超长文处理的新里程碑

【文末附gpt升级秘笈】腾讯元宝AI搜索解析能力升级：千万字超长文处理的新里程碑

腾讯元宝AI搜索解析能力升级：千万字超长文处理的新里程碑 一、引言 随着人工智能技术的飞速发展，自然语言处理（NLP）和机器学习（ML）在各行各业的应用日益广泛。其中，AI搜索解析能力作为信息检索和知识抽取的核心技术，受到了广泛的关注和研究。腾讯作为互联网行业的领军企业，其在AI领域的探索和创新一直走在前列。近日，腾讯旗下的AI大模型应用——腾讯元宝，迎来了1.1.7版本的升级，新版本在AI搜
阅读更多...
拓扑排序——C语言

拓扑排序——C语言

拓扑排序（Topological Sorting）是一种用于有向无环图（DAG）的排序算法，其输出是图中所有顶点的线性排序，使得对于每条有向边 (u, v)，顶点 u 在 v 之前出现。拓扑排序确定了项目网络图中的起始事件和终止事件，也就是顶点的执行顺序。         因为是有向无环图，所以拓扑排序的作用其实就是把先发生的排序在前面，后发生的排序到后面。 例如现在我们有一个
阅读更多...
CALayer相关的属性

CALayer相关的属性

iOS开发UI篇—CAlayer层的属性 一、position和anchorPoint 1.简单介绍 CALayer有2个非常重要的属性：position和anchorPoint @property CGPoint position; 用来设置CALayer在父层中的位置 以父层的左上角为原点(0, 0)   @property CGPoint anchorPoint; 称为“定位点”、“锚点”
阅读更多...
Avalonia 常用控件二 Menu相关

Avalonia 常用控件二 Menu相关

1、Menu 添加代码如下 <Button HorizontalAlignment="Center" Content="Menu/菜单"><Button.Flyout><MenuFlyout><MenuItem Header="打开"/><MenuItem Header="-"/><MenuItem Header="关闭"/></MenuFlyout></Button.Flyout></B
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2