C++ 二叉搜索树练习

目录

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

2.二叉搜索树与双向链表

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

 4.非递归实现二叉树的前序遍历

 5.非递归实现二叉树的中序遍历

6.非递归实现二叉树的后序遍历

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

略

2.二叉搜索树与双向链表

二叉搜索树与双向链表_牛客题霸_牛客网

按照中序的方式遍历，左指针的链接方式如图

class Solution {
public:void InOrderConvert(TreeNode* cur,TreeNode*& prev){if(cur == nullptr)return;InOrderConvert(cur->left,prev);cur->left = prev;if(prev)prev->right = cur;prev = cur;InOrderConvert(cur->right,prev);}TreeNode* Convert(TreeNode* pRootOfTree) {if(pRootOfTree == nullptr)return nullptr;TreeNode* prev = nullptr;InOrderConvert(pRootOfTree,prev);TreeNode* head = pRootOfTree;while(head->left)head = head->left;return head;}
};

函数递归展开图如下 

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

力扣

class Solution {
public:TreeNode* _buildTree(vector& preorder, vector& inorder,int& prei,int inBegin,int inEnd) {if(inBegin>inEnd)return nullptr;TreeNode* root = new TreeNode(preorder[prei]);++prei;size_t rooti = inBegin;while(rooti<=inEnd){if(root->val == inorder[rooti])break;else++rooti;}root->left = _buildTree(preorder,inorder,prei,inBegin,rooti-1);root->right = _buildTree(preorder,inorder,prei,rooti+1,inEnd);return root;}TreeNode* buildTree(vector&preorder,vector&inorder){int prei = 0,inBegin = 0,inEnd = inorder.size()-1;return _buildTree(preorder,inorder,prei,inBegin,inEnd);}
};

递归展开图如下 

 4.非递归实现二叉树的前序遍历

力扣

class Solution {
public:vector preorderTraversal(TreeNode* root) {vector v;stack st;TreeNode* cur = root;while(cur||!st.empty()){while(cur){v.push_back(cur->val);st.push(cur);cur = cur->left;}TreeNode* top = st.top();st.pop();cur = top->right;}return v;}
};

 5.非递归实现二叉树的中序遍历

力扣

class Solution {
public:vector inorderTraversal(TreeNode* root) {vector v;stackst;TreeNode* cur = root;while(cur || !st.empty()){while(cur){st.push(cur);cur = cur->left;}TreeNode* top = st.top();st.pop();v.push_back(top->val);cur = top->right;}return v;}
};

6.非递归实现二叉树的后序遍历

力扣

class Solution {
public:vector postorderTraversal(TreeNode* root) {vector v;stack st;TreeNode*prev = nullptr;TreeNode* cur = root;while(cur || !st.empty()){while(cur){st.push(cur);cur = cur->left;}TreeNode* top = st.top();if(top->right == nullptr || top->right == prev){v.push_back(top->val);st.pop();prev = top;}else{cur = top->right;}}return v;} 
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！