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

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

Solution1：

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
static int flag = 0;
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 1.找到从根节点到某一结点的路径。存储在栈内。
        stack<TreeNode*> a;
        stack<TreeNode*> b;
        flag = 0;
        path(root,p,a);
        flag = 0;
        path(root,q,b);

        // 2.比较两个栈的栈顶，一样，返回，不一样，弹出较长的那个。如果长度一样，同时弹出。
        TreeNode* t = NULL;
        while(1){
            if(a.top() == b.top()){
                t = a.top();
                break;
            }
            if(a.size() > b.size()){
                a.pop();
            }else if(a.size() < b.size()){
                b.pop();
            }else{
                a.pop();
                b.pop();
            }
        }
        return t;
    }
    
    void path(TreeNode* root, TreeNode* p, stack<TreeNode*> &a){
        if(!root || flag == 1) return;
        a.push(root);
        if(root == p){
            flag = 1;
        } 
        path(root->left,p,a);
        path(root->right,p,a);
        if(flag != 1){
            a.pop();
        }
    }
};
先寻找从根节点到给定结点的路径，并存储在栈中。
再将两栈比较，找到第一个相同结点即为最近公共祖先。

由于需要找最近相同的结点。
所以在遍历二叉树时，要使用前序遍历，先将结点保存在栈中，再考虑其子节点。
得到两个存储路径的栈（根节点在栈底）。

由于路径与层有关，路径越长的结点，所在的层也越低。所以寻找公共结点首先把较大的栈缩小到与较小的栈长度一致，然后比较栈顶，当遇到相同结点时，就为最近公共祖先。

Solution2：

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
/**
 * Definition for a binary tree node.
 * 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 || root == p || root == q) return root;
        TreeNode* left = lowestCommonAncestor(root->left,p,q);
        TreeNode* right = lowestCommonAncestor(root->right,p,q);
        // 如果找到了两个结点，不在一个位置。返回该结点（该结点是两个结点的公共祖先）。
        if(left && right) return root;
        
        //如果在该结点的下面，只找到了一个，先将该结点返回，交给上一级处理。（为了递归）
        if(left) return left;
        else return right;
        
    }
};

递归版本。

看了评论区大神写的。