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

解法1

规则：

一个是左子树中的节点，一个是右子树中的节点，那么他就是最近的公共祖先

这种做法的时间复杂度是O(H*N)，如果公共祖先在很下面，时间复杂度就比较高

每次找高度次

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
class Solution {
public:
    bool Find(TreeNode* root, TreeNode* x)
    {
        if(root==nullptr)
            return false;
        /*if(root==x)
            return true;

        if(Find(root->left, x))
            return true;
        if(Find(root->right,x))
            return true;
        return false;*/
	    //更好的写法
	    retur root==x||Find(root->left,x)||Find(root->right,x);
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==nullptr)
        {
            return nullptr;
        }

        if(root==p||root==q)
            return root;
        
        bool pInLeft,pInRight,qInLeft,qInRight;
        pInLeft=Find(root->left, p);
        pInRight=!pInLeft;

        qInLeft=Find(root->left, q);
        qInRight=!qInLeft;
        //1、一个在左一个在右，root就是最近公共祖先
        //2、都在左，递归去左子树找
        //3、都在右，递归去右子树找
        if((pInLeft&&qInRight)||(pInRight&&qInLeft))
        {
            return root;
        }
        else if(pInLeft&&qInLeft)
        {
            return lowestCommonAncestor(root->left, p, q);
        }
        else if(pInRight&&qInRight)
        {
            return lowestCommonAncestor(root->right, p, q);
        }
        else
        {
            return nullptr;
        }
    }
};pp

解法2

用栈记录路径，时间复杂度为O(N)

找6的路径

找4的路径

我自己写的

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
72
73
74
class Solution {
public:

    bool find(TreeNode* root, TreeNode* x, stack<TreeNode*>& s)
    {
        if(root==nullptr)
        {
            return false;
        }


        s.push(root);

        if(root==x)
        {
            return true;
        }

        if(find(root->left, x, s))
        {
            return true;
        }

        if(find(root->right, x ,s))
        {
            return true;
        }

        s.pop();
        return false;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        stack<TreeNode*>s1;
        stack<TreeNode*>s2;
        find(root,p, s1);
        find(root,q, s2);

        // while(!s1.empty())
        // {
        //     cout<<s1.top()->val<<" ";
        //     s1.pop();
        // }
        // cout<<endl;
        // while(!s2.empty())
        // {
        //     cout<<s2.top()->val<<" ";
        //     s2.pop();
        // }
        // cout<<endl;
        while(!s1.empty()&&!s2.empty())
        {
            if(s1.top()==s2.top())
            {
                return s2.top();
            }

            if(s1.size()==s2.size())
            {
                s1.pop();
                s2.pop();
            }
            else if(s1.size()>s2.size())
            {
                s1.pop();
            }
            else
            {
                s2.pop();
            }
        }

        return nullptr;
    }
};