沧州网站建设的集成商,东莞建设专业网站,新闻头条今天最新消息,乐清柳市网站建设公司1--二叉树的最近公共祖先 主要思路#xff1a; 最近祖先只有两种情况#xff1a;① 自底向上#xff0c;当两个目的结点分别在当前结点的左右子树时#xff0c;当前结点为两个目的结点的最近祖先#xff1b;② 最近祖先与其中一个目的结点相同#xff0c;则另一个目的结点…1--二叉树的最近公共祖先 主要思路 最近祖先只有两种情况① 自底向上当两个目的结点分别在当前结点的左右子树时当前结点为两个目的结点的最近祖先② 最近祖先与其中一个目的结点相同则另一个目的结点在目的结点的子树上 递归寻找目的结点当找到目的结点后往上返回目的结点否则返回 NULL当一个结点在左右子树上分别找到了两个目的结点表明这个结点是最近祖先否则返回不为空的子树的返回结点这时两个结点对应第 ② 种情况 #include iostream
#include vector
#include stackstruct 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 NULL || root-val p-val || root-val q-val) return root;TreeNode* left lowestCommonAncestor(root-left, p, q);TreeNode* right lowestCommonAncestor(root-right, p, q);if(left ! NULL right ! NULL) return root;else if( left ! NULL) return left;else return right;}
};int main(int argc, char *argv[]){TreeNode *Node1 new TreeNode(3);TreeNode *Node2 new TreeNode(5);TreeNode *Node3 new TreeNode(1);TreeNode *Node4 new TreeNode(6);TreeNode *Node5 new TreeNode(2);TreeNode *Node6 new TreeNode(0);TreeNode *Node7 new TreeNode(8);TreeNode *Node8 new TreeNode(7);TreeNode *Node9 new TreeNode(4);Node1-left Node2;Node1-right Node3;Node2-left Node4;Node2-right Node5;Node3-left Node6;Node3-right Node7;Node5-left Node8;Node6-right Node9;Solution S1;TreeNode* res S1.lowestCommonAncestor(Node1, Node2, Node9);std::cout res-val std::endl;return 0;
}
2--二叉搜索树的中序后继结点 主要思路 如果 p 结点有右子树则返回其右子树最左边的结点中序遍历的定义 如果 p 结点没有右子树则从 root 结点开始寻找 p 结点的父亲结点根据二叉搜索树的定义可以节省寻找的时间只需在一边进行寻找 #include iostream
#include vector
#include stackstruct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};class Solution {
public:TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {TreeNode *res NULL;if(p-right ! NULL){ // p的中序后继是其右子树上最左的结点即右字数上最先返回的结点res p-right;while(res-left ! NULL) res res-left;return res;}// p没有右子树从root结点开始搜索p的父亲结点while(root ! NULL){if(root-val p-val){ // p在左子树上res root;root root-left; // 在左子树上找到最后一个比p大的结点中序遍历是有序的中序后继结点表明是比p结点大}else{root root-right; // p在右子树上}}return res;}
};int main(int argc, char *argv[]){TreeNode *Node1 new TreeNode(2);TreeNode *Node2 new TreeNode(1);TreeNode *Node3 new TreeNode(3);Node1-left Node2;Node1-right Node3;Solution S1;TreeNode* res S1.inorderSuccessor(Node1, Node2);std::cout res-val std::endl;return 0;
}
3--二叉树的序列化与反序列化 主要思路 利用前序遍历或层次遍历等方式进行序列化再根据不同遍历的方式来设计反序列化的方式利用反序列化重构二叉树 下面的代码使用了层次遍历进行序列化并通过类似层次遍历的方式进行反序列化重构二叉树 #include iostream
#include string
#include vector
#include queuestruct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};class Codec {
public:std::string serialize(TreeNode* root) {std::string res ;if (root NULL) return res;std::queueTreeNode* q;q.push(root);res std::to_string(root-val) ,;while(!q.empty()){TreeNode* tmp q.front();q.pop();if(tmp-left ! NULL){q.push(tmp-left);res std::to_string(tmp-left-val) ,;}else res #,;if(tmp-right ! NULL){q.push(tmp-right);res std::to_string(tmp-right-val) ,;}else res #,;}return res;}TreeNode* deserialize(std::string data) {if (data.length() 0) return NULL;std::vectorstd::string value;for(auto i 0; i data.length(); i){std::string tmp ;while(data[i] ! ,){tmp data[i];i;}value.push_back(tmp);}TreeNode *res new TreeNode(std::stoi(value[0]));std::queueTreeNode* q;q.push(res);int idx 1;while(!q.empty()){TreeNode* tmp q.front();q.pop();if(value[idx] ! #){ // 左儿子tmp-left new TreeNode(std::stoi(value[idx]));q.push(tmp-left);} idx;if(value[idx] ! #){ // 右儿子tmp-right new TreeNode(std::stoi(value[idx]));q.push(tmp-right);} idx;}return res;}
};void printTreeNode(TreeNode *root){if (root NULL) return;std::queueTreeNode* q;q.push(root);std::cout root-val ;while(!q.empty()){TreeNode* tmp q.front();q.pop();if(tmp-left ! NULL){q.push(tmp-left);std::cout tmp-left-val ;}else std::cout null ;if(tmp-right ! NULL){q.push(tmp-right);std::cout tmp-right-val ;}else std::cout null ;}
}int main(int argc, char *argv[]){//root [1,2,3,null,null,4,5]TreeNode *Node1 new TreeNode(1);TreeNode *Node2 new TreeNode(2);TreeNode *Node3 new TreeNode(3);TreeNode *Node4 new TreeNode(4);TreeNode *Node5 new TreeNode(5);Node1-left Node2;Node1-right Node3;Node3-left Node4;Node3-right Node5;Codec S1;std::cout S1.serialize(Node1) std::endl;TreeNode *res S1.deserialize(S1.serialize(Node1));printTreeNode(res);return 0;
}
