二叉樹的最近公共祖先

思路

1. 在左、右子樹中分別查找是否包含p或q：
2. 如果以下兩種情況（左子樹包含p，右子樹包含q/左子樹包含q，右子樹包含p），那么此時的根節點就是最近公共祖先
3. 如果左子樹包含p和q，那么到root->left中繼續查找，最近公共祖先在左子樹里面
4. 如果右子樹包含p和q，那么到root->right中繼續查找，最近公共祖先在右子樹里面

 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 == nullptr || root == p || root == q){return root;}TreeNode* left = lowestCommonAncestor(root->left, p, q);TreeNode* right = lowestCommonAncestor(root->right, p, q);return left == nullptr ? right : (right == nullptr ? left : root);}
};

二叉樹搜索樹轉換成排序雙向鏈表

二叉搜索樹：普通的二叉樹

1. 左子樹所有結點小于根
2. 右子樹所有結點大于根
3. 中序有序

Node *prev = NULL;
void func(Node *node){node->left = prev;	//等于上面的node->prev;if(prev != NULL){prev->right = node ; //等于上面的prev->next}prev = node;
}void inorder(Node *root){if(root == NULL)return ;inorder(root->left);func(root);inorder(root->right);
}

class Solution {
public:TreeNode *prev = NULL;TreeNode *first ;void fun(TreeNode * node){node->left =prev;if(prev!=NULL){prev->right = node;}else{first = node;}prev =node;}void Inorder(TreeNode *root){if(root == NULL){return ;}Inorder(root->left);fun(root);Inorder(root->right);}TreeNode* Convert(TreeNode* pRootOfTree){first = NULL;Inorder(pRootOfTree);return first;}
};