一、二叉搜索树的最近公共祖先

• 对于有根树T，的连个节点，p1,p2,其公共祖先为x,且x的深度要尽可能大
• 一个节点也可以是自己的祖先
• 二叉搜索树所有节点值都是唯一的，可通过节点值直接比较

解法一:二次遍历(推荐)

• 利用二叉搜索数的性质，从根节点开始查找目标，当前节点比目标小则进右子树，大则进左子树，直到找到目标节点，用数组记录遇到的元素
• 分别再二叉搜索树中找到p1,p2这两个节点，并用数组记录各自路径
• 同时遍历两个数组，比较节点值，最后一个相等的元素就是最近的公共祖先

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param p int整型 
     * @param q int整型 
     * @return int整型
     */
    vector<int>getPath(TreeNode*root,int target)
    {
        vector<int>v;
        TreeNode*node=root;
        while(node->val!=target)
        {
            v.push_back(node->val);
            if(target<node->val)//小的在左
                node=node->left;
            else//大的在右
                node=node->right;
        }
        v.push_back(node->val);
        return v;
    }
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        // write code here
        vector<int>p1=getPath(root, p),p2=getPath(root,q);
        int target;
        //比较两个路径，找到第一个不同点
        for(int i=0;i<min(p1.size(),p2.size());i++)
        {
            if(p1[i]==p2[i])
                target=p1[i];//最后一个相同节点即为公共值
            else
                break;
        }
        return target;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

时间复杂度:O(n),最坏情况，二叉树退化为链表，搜到目标需要O(n),比较路径前半段相同的也需要O(n)
空间复杂度:O(n),记录路径数组最长为n

解法二:一次遍历

若p,q都小于等于这个节点值，则p,q都在该节点的左子树，反之右子树，若一个大一个小，则该节点即为公共祖先，只有最近公共祖先会将p,q放入不同的子树，采用递归求解

• 优先判断空
• 对某一节点，与p,q比较大小，据上描述判断
• 若p,q都在该节点左边，递归进左子树，
• 反之进右子树

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param p int整型 
     * @param q int整型 
     * @return int整型
     */
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        // write code here
        if(root==NULL)
            return -1;
        if((p>=root->val&&q<=root->val)||(p<=root->val&&q>=root->val))//两边不同公共祖先
            return root->val;
        else if(p<=root->val&&q<=root->val)
            return lowestCommonAncestor(root->left, p, q);//小于向左递归
        else
            return lowestCommonAncestor(root->right,  p, q);//大于向右
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

时间复杂度:O(n),最坏遍历二叉树所有节点
空间复杂度:O(n),递归栈深度最坏为n

二、 在二叉树中找到两个节点的最近公共祖先

题目保证了二叉树节点值都不同

解法一:路径比较法(推荐)

• 利用dfs求得根节点到两个目标节点的路径，每次选择二叉树的一棵子树往下找，同时存储路径的数组增加遍历的节点值，当叶子节点不存在时，回溯到父节点，寻找其他路径，回溯时去掉数组中刚加入的元素
• 遍历两条路径数组，比较元素值
• 两条路径的最后一个相同同节点即为最近公共祖先

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    bool flag =false;//记录是否找到路径
    void dfs(TreeNode*root,vector<int>&path,int target)
    {
        if(flag||root==NULL)
            return ;
        path.push_back(root->val);
        if(root->val==target)
        {
            flag=true;
            return ;
        }
        dfs(root->left,path,target);//dfs遍历查找
        dfs(root->right,path,target);
        if(flag)
            return ;
        path.pop_back();//还未找到路径，则该子树没有，回溯
    }
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // write code here
        vector<int>v1,v2;
        dfs(root,v1,o1);
        flag=false;//flag作为全局变量这里要重置
        dfs(root,v2,o2);
        int result;
        for(int i=0;i<min(v1.size(),v2.size());i++)
        {
            if(v1[i]==v2[i])
                result=v1[i];
            else
                break;
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

时间复杂度:O(n),n为节点数，先递归遍历节点求路径，后遍历路径找祖先
空间复杂度:O(n),最坏二叉树退化为链表，递归栈深度和路径数组大小为n

解法二:递归

• 若两节点的任意一个与根节点匹配，则root为最近公共祖先
• 若都不匹配，分别递归左子树，右子树
• 若一个节点在左子树，一个节点在右子树，则根节点为目标节点
• 若两个都在左子树，则向左递归，反之向右

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // write code here
        if(root==NULL)
            return -1;
        if(root->val==o1||root->val==o2)//匹配返回
            return root->val;
        int left=lowestCommonAncestor(root->left, o1, o2),
        right=lowestCommonAncestor(root->right, o1, o2);
        if(left==-1)//不在左就在右
            return right;
        if(right==-1)
            return left;
        return root->val;//否则·根为当前节点
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

时间复杂度:O(n),n为节点数，递归遍历节点
空间复杂度:O(n),最坏二叉树退化为链表，递归栈深度为n

三、序列化二叉树

遍历二叉树，记录节点，再用同样方式遍历时可以还原二叉树，其存储即为二叉树的序列化
遍历方法有四种:前、中、后、层序遍历

解法一:前序遍历(推荐)

• 优先处理序列化,使用序列化函数进行先序遍历，遇到空节点在字符串中添加#,非空添加节点值和’|'作为分割符，然后进入左，右子树递归
• 使用逆序列化函数先序递归构建子树，遇到’#'即为空节点，遇到数字根据‘|’分割，将字符串转化为数字后加入创建节点中，再分别创建左子树，右子树。

class Solution {
public:
    void SerializeFunctiion(TreeNode*root,string&str)
    {
        if(root==NULL)
        {
            str+='#';
            return ;
        }
        string tmp=to_string(root->val);//转化数字为字符的内置函数
        str+=tmp+'|';
        SerializeFunctiion(root->left, str);//递归序列化左右子树
        SerializeFunctiion(root->right, str);
    }
    char* Serialize(TreeNode *root) {    
        if(root==NULL)
            return "#";
        string tmp;
        SerializeFunctiion(root, tmp);
        char*transchar=new char[tmp.length()+1];//将string转化为char
        strcpy(transchar,tmp.c_str());
        transchar[tmp.length()]='\0';
        return transchar;
    }
    TreeNode*DeserializeFunction(char**str)
    {
        //到叶子节点时，创建完毕，返回继续创建父节点
        if(**str=='#')
        {
            (*str)++;
            return NULL;
        }
        //将字符转化为数字
        int val=0;
        while(**str!='|'&&**str!='|')
        {
            val=val*10+((**str)-'0');
            (*str)++;
        }
        TreeNode*root=new TreeNode(val);
        if(**str=='\0')//到底创创建完毕，返回结果
            return root;
        else
            (*str)++;
        root->left=DeserializeFunction(str);//左右子树分别反序列化
        root->right=DeserializeFunction(str);
        return root;
    }
    TreeNode* Deserialize(char *str) {
        if(*str=='#')
            return NULL;
        TreeNode*node=DeserializeFunction(&str);
        return node;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

时间复杂度:O(n),先序遍历节点
空间复杂度:O(n),递归栈最大深度

解法二:层序遍历

class Solution {
public:
    char* Serialize(TreeNode *root) {    
        string ret;
        if(!root) 
            return NULL;
        queue<TreeNode*> q;
        q.emplace(root);    // 根结点入队
        ret += to_string(root->val) + '|';    // 记录节点值
        while(!q.empty()){
            TreeNode* p = q.front(); 
            q.pop();   
            if(p->left){    // 若不为空，加上"val" + "!"
                ret += to_string(p->left->val) + '|';
                q.emplace(p->left);
            }
            else ret += '#';    // 为空加上'#'

            if(p->right){
                ret += to_string(p->right->val) + '|';
                q.emplace(p->right);
            }
            else ret += '#';
        }
        char* transchar = new char[ret.size() + 1];
        strcpy(transchar, ret.c_str());
        return transchar;
    }

    TreeNode* Deserialize(char *str) {
        if(!str) 
            return NULL;
        string data = string(str);
        vector<string> v;     // 先对data预处理一下

        for(int i = 0; i < data.size(); i++){
            if(data[i] == '#') 
                v.push_back(string("#"));    // 为空则用"#"表示
            else{
                int j = i;
                while(data[j] != '|') 
                j++;
                v.push_back(data.substr(i, j - i));    // 不为空则用"val"表示
                i = j;
            }
        }
        // stoi()函数可以将string转换为int
        TreeNode* root = new TreeNode(stoi(v[0]));    // 创建根节点
        queue<TreeNode*> q;
        q.emplace(root);    // 根节点入队
        int k = 1;
        while(k < v.size()){
            TreeNode* p = q.front(); 
            q.pop();
            TreeNode *left=NULL,*right=NULL;
            if(v[k] != "#"){    // 若左儿子非空
                left = new TreeNode(stoi(v[k]));
                q.emplace(left);
            }
            p->left = left;
            if(v[k + 1] != "#"){    // 若右儿子非空
                right= new TreeNode(stoi(v[k + 1]));
                q.emplace(right);
            }
            p->right = right;
            k += 2;    // 指针向后后移动两步
        }

        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

采用非递归的方式构建二叉树
时间复杂度：O(n), n为节点数，层序遍历一次的时间复杂度为O(n)
空间复杂度：O(n), 序列化使用了一个队列，反序列化使用了一个vector，时间复杂度为O(n)