1--二叉樹的最近公共祖先
主要思路：
? ? ? ? 最近祖先只有兩種情況：① 自底向上，當兩個目的結點分別在當前結點的左右子樹時，當前結點為兩個目的結點的最近祖先；② 最近祖先與其中一個目的結點相同，則另一個目的結點在目的結點的子樹上；
? ? ? ? 遞歸尋找目的結點，當找到目的結點后往上返回目的結點，否則返回 NULL；當一個結點在左右子樹上分別找到了兩個目的結點，表明這個結點是最近祖先；否則返回不為空的子樹的返回結點（這時兩個結點對應第 ② 種情況）；
#include <iostream>
#include <vector>
#include <stack>struct 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 <stack>struct 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 <queue>struct 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::queue<TreeNode*> 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::vector<std::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::queue<TreeNode*> 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::queue<TreeNode*> 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;
}
)